Boj 17469) 트리의 색깔과 쿼리

문제

백준 17469

설명

Smaller to Larger 를 사용하는 Offine Queries 의 전형적인 문제이다.

쿼리를 순차적으로 처리하면 쿼리를 처리하기가 난감하다. 하지만 거꾸로 처리하면 평범한 Union Find 문제로 바뀐다.

이때 합치는 과정에서 오버헤드를 줄이기 위해 작은 것부터 합치면 전체 과정을 O(\(\mathrm{N} \log{\mathrm{N}}\)) 에서 해결할 수 있다.

• 이에대한 증명은 Union Find 최적화 기법과 비슷하게 하면 된다.
• 작은 그룹을 움직이면 합쳐진 그룹은 이전 그룹의 두배 이상이 되므로, 임의의 원소가 움직이면 그것을 포함하는 그룹의 크기가 2배 이상이 된다. 이는 전체 크기를 넘지 못하므로 각 원소는 최대 \(\log{\mathrm{N}}\) 번 움직임이 보장된다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{N}}\))

코드

const int MAX_IN = 100020;
int parents[MAX_IN], roots[MAX_IN];
int queries[1000001 + MAX_IN];
unordered_set<int> groups[MAX_IN];
vector<int> ans;

int Find(int a)
{
	if (roots[a] == a) return a;
	return roots[a] = Find(roots[a]);
}

void Union(int from, int to)
{
	from = Find(from);
	to = Find(to);
	roots[from] = to;
}

int main()
{
	int n, q;
	cin >> n >> q;
	for (int i = 2; i <= n; i++) cin >> parents[i];
	for (int i = 1; i <= n; i++) { int c;  cin >> c; groups[i].insert(c); roots[i] = i; }
	for (int i = 0; i < n + q - 1; i++) {
		int a, b; cin >> a >> b;
		queries[i] = (b << 1) + (a == 2);
	}
	for (int i = n + q - 2; i >= 0; i--)
	{
		int b = queries[i] >> 1, a = queries[i] & 1 ? 2 : 1;
		if (a == 1)
		{
			int from = Find(b), to = Find(parents[b]);
			if (from == to) continue;
			if (groups[from].size() < groups[to].size()) {
				Union(from, to);
				swap(from, to);
			}
			else Union(to, from);

			for (auto a : groups[to]) groups[from].insert(a);
			groups[to].clear();
		}
		else {
			ans.push_back(groups[Find(b)].size());
		}
	}
	for (auto iter = ans.rbegin(); iter != ans.rend(); iter++)
		cout << *iter << '\n';
}