boj) 15782 Calculate! 2

15782.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

vector<int> seg_tree, lazy, p(1), weight;
vector<vector<int>> ori_tree;
int n, m, numChild[100001], numbering[100001];
bool check[100001];

int init_seg_data(int now) {
	check[now] = true;
	int child = 0;
	for (int next : ori_tree[now]) {
		if(!check[next])
			child += init_seg_data(next);
	}
	numbering[now] = p.size();
	p.push_back(weight[now]);
	numChild[now] = child;
	return child + 1;
}

void init_seg_tree(int node, int start, int end) {
	if (start == end) {
		seg_tree[node] = p[start];
	}
	else {
		init_seg_tree(node * 2, start, (start + end) / 2);
		init_seg_tree(node * 2 + 1, (start + end) / 2 + 1, end);
		seg_tree[node] = seg_tree[node * 2] ^ seg_tree[node * 2 + 1];
	}
}

void update_lazy(int node, int start, int end) {
	if (lazy[node]) {
		if ((end - start + 1) & 1)
			seg_tree[node] ^= lazy[node];
		if (start != end) {
			lazy[node * 2] ^= lazy[node];
			lazy[node * 2 + 1] ^= lazy[node];
		}
		lazy[node] = 0;
	}
}
void update_range(int node, int start, int end, int i, int j, int diff) {
	update_lazy(node, start, end);
	if (start > j || end < i)
		return;
	else if (i <= start && end <= j) {
		if ((end - start + 1) & 1)
			seg_tree[node] ^= diff;
		if (start != end) {
			lazy[node * 2] ^= diff;
			lazy[node * 2 + 1] ^= diff;
		}
		return;
	}
	update_range(node * 2, start, (start + end) / 2, i, j, diff);
	update_range(node * 2 + 1, (start + end) / 2 + 1, end, i, j, diff);
	seg_tree[node] = seg_tree[node * 2] ^ seg_tree[node * 2 + 1];
}
int query(int node, int start, int end, int i, int j) {
	update_lazy(node, start, end);
	if (start > j || end < i)
		return 0;
	else if (i <= start && end <= j) {
		return seg_tree[node];
	}
	return query(node * 2, start, (start + end) / 2, i, j) ^ query(node * 2 + 1, (start + end) / 2 + 1, end, i, j);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	weight.resize(n + 1);
	ori_tree.resize(n + 1);
	int h = (int)ceil(log2(n));
	int tree_size = (1 << (h + 1));
	seg_tree.resize(tree_size);
	lazy.resize(tree_size);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		ori_tree[u].push_back(v);
		ori_tree[v].push_back(u);
	}
	for (int i = 1; i < n + 1; i++) {
		cin >> weight[i];
	}
	init_seg_data(1);

	init_seg_tree(1, 1, n);
	
	while (m--) {
		int cmd, x, y;
		cin >> cmd;
		if (cmd == 1) { // x포함 자손들의 가중치의 XOR값 출력
			cin >> x;
			cout << query(1, 1, n, numbering[x] - numChild[x], numbering[x]) << '\n';
		}
		else if (cmd == 2) { // 구간업데이트, y를 XOR
			cin >> x >> y;
			update_range(1, 1, n, numbering[x] - numChild[x], numbering[x], y); 
			
		}
	}
}