백준13309 트리

작성일 | In

문제 링크

  • http://icpc.me/13309

문제 출처

  • 2016 전국 본선 고등3

사용 알고리즘

  • HLD

시간복잡도

  • O(Qlog2N)

풀이

문제를 보고 HLD가 떠올라서 풀이를 구체화시킨 결과, 두 가지 풀이가 생각이 났습니다.

두 가지 풀이의 공통점은 처음에는 모든 간선의 가중치를 1로 주고, 간선을 끊는 행위는 간선의 가중치를 0으로 바꾸는 것으로 대체한다는 것 입니다.

첫 번째 방법을 먼저 설명드리겠습니다.
HLD를 두 개 만듭니다. 첫 번째 HLD는 간선을 끊을 때마다 가중치를 0으로 업데이트해주고, 두 번째 HLD는 가만히 둡니다. 쿼리는 경로 상에 있는 모든 간선의 가중치의 합을 반환하게 합니다.
u에서 v까지의 경로에 대해 두 개의 HLD 모두 쿼리를 날린 결과가 같으면 중간에 끊어진 간선이 없다는 것을 의미하므로 yes, 다르면 no입니다.

이 풀이는 HLD를 2개 사용하므로 시간이 약간 낭비됩니다. 두 번째 풀이를 소개하겠습니다.
이번에는 HLD를 하나만 쓰고, 쿼리는 덧셈 연산이 아닌 논리곱(&&) 연산으로 정의합니다. 이렇게 하면 경로 상에 있는 간선의 가중치가 모두 1인 경우에만 true를 반환하고, 하나라도 0이라면 false를 반환합니다.
이 풀이는 첫 번째 풀이에 비해 절반정도의 시간을 소모합니다.

아래 코드는 두 번째 풀이에 대한 코드입니다.

전체 코드

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

template <typename T>
class SegTree{
	private:
		T tree[808080];
		int lim;
		function<T(const T a, const T b)> f;
	public:
		void init(int n, function<T(const T a, const T b)> func){
			f = func;
			for(lim = 1; lim <= n; lim <<= 1);
		}
		void update(int x, T v){
			x += lim;
			tree[x] = v;
			while(x > 1){
				x >>= 1;
				tree[x] = f(tree[2*x], tree[2*x+1]);
			}
		}
		T query(int s, int e){
			s += lim;
			e += lim;
			T ret = 1;
			while(s < e){
				if(s%2 == 1) ret = f(ret, tree[s++]);
				if(e%2 == 0) ret = f(ret, tree[e--]);
				s >>= 1;
				e >>= 1;
			}
			if(s == e) ret = f(ret, tree[s]);
			return ret;
		}
};

template <typename T>
class HLD{
	private:
		int dn;
		int par[202020], size[202020], depth[202020], lab[202020];
		int id[202020], top[202020];
		SegTree<T> tree;
		function<T(const T a, const T b)> f;

		int dfs(int now, int prv){
			par[now] = prv; size[now] = 1;
			for(auto &t: g[now]){
				int nxt = t.first;
				if(nxt != prv){
					depth[nxt] = depth[now] + 1;
					size[now] += dfs(nxt, now);
				}
			}
			return size[now];
		}
		void decom(int now, int prv, int chain){
			lab[now] = dn;
			id[dn] = chain;
			top[chain] = dn++;
			int heavy = -1;
			for(auto &t: g[now]){
				int nxt = t.first;
				if(nxt != prv && (heavy == -1 || size[nxt] > size[heavy])) heavy = nxt;
			}
			if(heavy != -1) decom(heavy, now, chain);
			for(auto &t: g[now]){
				int nxt = t.first;
				if(nxt != prv && nxt != heavy) decom(nxt, now, nxt);
			}
		}

	public:
		vector<p> g[202020];

		void init(int root, function<T(const T a, const T b)> func){
			//init value
			f = func;
	    	dn = 0;
	    	memset(id,-1,sizeof(id));
			memset(top,-1,sizeof(top));

			//pre-processing
	    	dfs(root,-1);
			decom(root,-1,root);

			//set edge's weight
			vector<T> a(202020);
			for(int i=0;i<202020;i++){
				for(auto &t: g[i]){
					int next = t.first, w = t.second;
					int v = lab[next];
					if(depth[i] < depth[next]) a[v] = w;
				}
			}
			tree.init(a.size(), f);
			for(int i=0; i<a.size(); i++) tree.update(i, a[i]);
		}

		void update(int u, int v, T k){
			if(depth[u] < depth[v]) swap(u, v);
			tree.update(lab[u], k);
		}

		T query(int u, int v){
			T ret = 1;
			u = lab[u], v = lab[v];
			while(id[u] != id[v]){
				int uHead = id[u], vHead = id[v];
				if(depth[uHead] > depth[vHead]){
					ret = f(ret, tree.query(lab[uHead], u));
					u = lab[par[uHead]];
				}
				else{
					ret = f(ret,tree.query(lab[vHead], v));
					v = lab[par[vHead]];
				}
			}
			ret = f(ret, tree.query(min(u, v)+1, max(u,v)));
			return ret;
		}
};

HLD<int> hld;
vector<int> par(202020);

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for(int i=2; i<=n; i++){
		int t; cin >> t;
		par[i] = t;
		hld.g[t].push_back({i, 1});
	}
	hld.init(1, [](int a, int b){
		return a && b;
	});

	while(q--){
		int a, b, op; cin >> a >> b >> op;
		int res = hld.query(a, b);
		if(res) cout << "YES\n";
		else cout << "NO\n";
		if(op == 1){
			if(res) hld.update(a, par[a], 0);
			else hld.update(b, par[b], 0);
		}
	}
}