백준13306 트리

작성일 | In

문제 링크

  • http://icpc.me/13306

문제 출처

  • 2016 KOI 전국 본선 중등부3

사용 알고리즘

  • Union-Find

시간복잡도

  • O(Q * a(N))

풀이

정점이 n개인 트리에서 간선 n-1개를 제거한다는 것은 모든 정점을 따로 놓겠다는 의미입니다.
그러면, 간선을 제거해서 정점을 분리하는 것 대신 쿼리를 역으로 받아서 붙여주는 동작을 통해 구현할 수 있습니다.
정점들을 붙여주는 행위는 정점들을 그룹으로 묶는 것을 의미하기 때문에 Union-Find를 이용해 쉽게 구현할 수 있습니다.
Union by Rank와 Path Compression을 이용해 Union-Find의 시간 복잡도를 최적화해주면 주어진 시간 이내에 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

int parent[200020];
int level[200020];
int g[200020];
int n;

int query[400010][3];

void init(){
	for(int i=0; i<=200000; i++){
		parent[i] = i;
		level[i] = 1;
	}
}

int find(int u){
	if(u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

void merge(int u, int v){
	u = find(u);
	v = find(v);

	if(u == v) return;
	if(level[u] > level[v]) swap(u, v);
	parent[u] = v;
	if(level[u] == level[v]) level[v]++;
}

int main(){
	ios_base::sync_with_stdio(0); //cin.tie(0);
	int n, q; cin >> n >> q;
	g[1] = 1;
	for(int i=2; i<=n; i++){
		int t; cin >> t;
		g[i] = t;
	}
	init();
	q += (n-1);
	for(int i=0; i<q; i++){
		int op; cin >> op;
		if(op) cin >> query[i][1] >> query[i][2];
		else{
			cin >> query[i][1]; query[i][2] = 0;
		}
	}
	stack<bool> s;
	for(int i=q-1; i>=0; i--){
		if(query[i][2]){
			if(find(query[i][1]) == find(query[i][2])) s.push(true);
			else s.push(false);
		}else{
			merge(query[i][1], g[query[i][1]]);
		}
	}


	while(!s.empty()){
		cout << (s.top()?"YES":"NO") << "\n"; s.pop();
	}

	return 0;
}