[C++] 백준 15782번 Calculate! 2

문제 링크

15782번: Calculate! 2

문제 요약

10만개 이하의 정점을 가진 트리에 대해 다음의 두 가지 쿼리를 수행해야 한다.
수행할 쿼리의 수는 50만개 이하이다.
1. 정점 x를 포함한 모든 자손들의 가중치를 XOR한 값 출력
2. 정점 x의 모든 자손들의 가중치에 대해 y를 XOR 연산 수행

접근 방법

회사 문화 시리즈와 XOR을 합친 것 같은 문제였습니다.

기본적으로 세그먼트 트리를 사용했습니다. 먼저 오일러 경로 테크닉을 이용해서 세그먼트 트리와 in, out 배열을 초기화 해줍니다. 그 다음에 in, out 배열을 이용해서 구간 쿼리를 수행해 주면 됩니다. 다만 두번째 쿼리가 구간을 갱신할 필요가 있기 때문에 lazy propagation이 필요합니다.
난이도 기여를 보니 lazy propagation이 필요 없는 풀이도 있는 것 같습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 100001

using namespace std;

int n, m, idx = 0;
vector<int> adj[MAX], lazy, tree, in, out;

void dfs(int now, int parent)
{
	in[now] = ++idx;
	for (auto& next : adj[now])
		if (next != parent)
			dfs(next, now);
	out[now] = idx;
}

void propagate(int node, int start, int end)
{
	if (lazy[node])
	{
		tree[node] ^= lazy[node] * ((end - start + 1) % 2);
		if (start != end)
			lazy[node * 2] ^= lazy[node], lazy[node * 2 + 1] ^= lazy[node];
		lazy[node] = 0;
	}
}

void update(int node, int start, int end, int left, int right, int val)
{
	propagate(node, start, end);
	if (start > right || end < left)
		return;
	if (start >= left && end <= right)
	{
		tree[node] ^= val * ((end - start + 1) % 2);
		if (start != end)
			lazy[node * 2] ^= val, lazy[node * 2 + 1] ^= val;
		return;
	}
	update(node * 2, start, (start + end) / 2, left, right, val);
	update(node * 2 + 1, (start + end) / 2 + 1, end, left, right, val);
	tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
}

int XOR(int node, int start, int end, int left, int right)
{
	propagate(node, start, end);
	if (start > right || end < left)
		return 0;
	if (start >= left && end <= right)
		return tree[node];
	return XOR(node * 2, start, (start + end) / 2, left, right) ^ XOR(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
}

int main(void)
{
	FASTIO;
	cin >> n >> m;

	in.resize(n + 1);
	out.resize(n + 1);

	int treeSize = ceil(log2(n + 1)) + 1;
	tree.resize(1 << treeSize);
	lazy.resize(1 << treeSize);

	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	dfs(1, 0);

	for (int i = 1; i <= n; i++)
	{
		int num;
		cin >> num;
		update(1, 1, n, in[i], in[i], num);
	}

	while (m--)
	{
		int query;
		cin >> query;

		if (query == 1)
		{
			int x;
			cin >> x;
			cout << XOR(1, 1, n, in[x], out[x]) << endl;
		}
		else
		{
			int x, y;
			cin >> x >> y;
			update(1, 1, n, in[x], out[x], y);
		}
	}

	return 0;
}