백준13512 트리와 쿼리 3

작성일 | In

문제 링크

  • http://icpc.me/13512

사용 알고리즘

  • HLD
  • 세그 트리

풀이

검은 색 정점을 1, 흰색 정점을 0으로 표현하면서 구간 합을 구하는 segment tree를 구축해줍시다.
첫 번째로 나오는 검정 정점의 번호는 세그 트리로 k번째 원소를 아이디어를 사용하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

vector<int> inp[101010];
vector<int> g[101010];

int dep[101010], sz[101010], top[101010], tail[101010], in[101010], par[101010], rev[101010];
int chk[101010], pv;

int tree[1 << 18];
int bias = 1 << 17;

void seg_update(int x, int v){
	x |= bias; tree[x] = v;
	while(x >>= 1){
		tree[x] = tree[x << 1] + tree[x << 1 | 1];
	}
}

int seg_get(int x){
	return tree[bias | x];
}

int seg_sum(int l, int r){
	l |= bias, r |= bias;
	int ret = 0;
	while(l <= r){
		if(l & 1) ret += tree[l++];
		if(~r & 1) ret += tree[r--];
		l >>= 1, r >>= 1;
	}
	return ret;
}

int seg_query(int l, int r){
	if(seg_sum(l, r) == 0) return -1;
	int ret = -1;
	while(l <= r){
		int m = l + r >> 1;
		if(seg_sum(l, m)){
			ret = m; r = m - 1;
		}
		else l = m + 1;
	}
	return ret;
}

void dfs(int v = 1){
	chk[v] = 1;
	for(auto i : inp[v]){
		if(chk[i]) continue;
		chk[i] = 1;
		dfs(i);
		g[v].push_back(i);
	}
}

void dfs1(int v = 1){
	sz[v] = 1;
	for(auto &i : g[v]){
		par[i] = v; dep[i] = dep[v] + 1;
		dfs1(i); sz[v] += sz[i];
		if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
	}
}

void dfs2(int v = 1){
	in[v] = ++pv; rev[pv] = v;
	for(auto i : g[v]){
		if(i == g[v][0]){
			top[i] = top[v];
			tail[top[v]] = i;
		}else{
			top[i] = tail[i] = i;
		}
		dfs2(i);
	}
}

int arr[101010];
int n, q;

void update(int x){
	arr[x] ^= 1;
	seg_update(in[x], arr[x]);
}

int query(int x){
	if(seg_get(1)) return 1;
	int ret = -1;
	while(top[x] != top[1]){
		int st = top[x];
		int now = seg_query(in[st], in[x]);
		if(now > 0) ret = now;
		x = par[st];
	}
	int now = seg_query(1, in[x]);
	if(now > 0) ret = now;
	return ret > 0 ? rev[ret] : -1;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<n; i++){
		int a, b; cin >> a >> b;
		inp[a].push_back(b);
		inp[b].push_back(a);
	}
	dfs(); dfs1(); dfs2();
	cin >> q;
	while(q--){
		int op, x; cin >> op >> x;
		if(op == 1){
			update(x);
		}else{
			cout << query(x) << "\n";
		}
	}
}