spoj QTREE3(树剖+线段树)

spoj QTREE3
树剖,然后线段树维护区间第一个出现的黑点。由于单点修改所以很简单了
(注意!树剖的$u,p_u,np_u$的意义要弄清楚!树剖时重点检查对象)

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 100000 + 5, INF = 1000000000;
int n, Q;
vector<int> G[MAXN];
void ins(int u, int v) {
G[u].push_back(v), G[v].push_back(u);
}
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN], p[MAXN], np[MAXN], top[MAXN], tb;
void dfs1(int u, int p) {
fa[u] = p, siz[u] = 1, dep[u] = dep[p] + 1;
for (int i = 0;i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != p) {
dfs1(v, u);
siz[u] += siz[v];
if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int chain) {
p[u] = ++tb;
np[p[u]] = u;
top[u] = chain;
if (son[u] != -1) {
dfs2(son[u], chain);
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != son[u] && v != fa[u]) {
dfs2(v, v);
}
}
}
}
#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)
int col[MAXN * 4], tag[MAXN * 4];
void pushup(int o) {
tag[o] = min(tag[lc], tag[rc]);
}
void update(int o, int l, int r, int x) {
if (l == r) {
col[o] = !col[o];
if (col[o] == 1) tag[o] = l;
else tag[o] = INF;
return ;
}
if (x <= M) update(lc, l, M, x);
else if (M < x) update(rc, M + 1, r, x);
pushup(o);
}
int query(int o, int l, int r, int x, int y) {
int ret = INF;
if (x <= l && r <= y) {
return tag[o];
}
if (x <= M) ret = min(ret, query(lc, l, M, x, y));
if (M < y) ret = min(ret, query(rc, M + 1, r, x, y));
return ret;
}
int find(int u, int v) {
int f1 = top[u], f2 = top[v], ret = INF;
while (f1 != f2) {
if (dep[f1] < dep[f2]) swap(u, v), swap(f1, f2);
ret = min(ret, query(1, 1, n, p[f1], p[u]));
u = fa[f1], f1 = top[u];
}
if (dep[u] < dep[v]) swap(u, v);
return min(ret, query(1, 1, n, p[v], p[u]));
}
void clean() {
tb = 0;
for (int i = 0; i <= 4 * n; i++) col[i] = 0, tag[i] = INF;
for (int i = 0; i <= n; i++) {
G[i].clear(), np[i] = p[i] = top[i] = fa[i] = dep[i] = 0, son[i] = -1;
}
}
void solve() {
clean();
for (int u, v, i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
ins(u, v);
}
dfs1(1, 0), dfs2(1, 1);
while (Q--) {
int opt, a;
scanf("%d%d", &opt, &a);
if (opt == 0) {
update(1, 1, n, p[a]);
} else {
int ans = find(1, a);
printf("%d\n", ans == INF ? -1 : np[ans]);
}
}
}
int main() {
//freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
scanf("%d%d", &n, &Q), solve();
return 0;
}
------ 本文结束 ------