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
| struct Link_Cut_Tree {
int fa[N], ch[N][2], sum[N], val[N], rev[N];
int stk[N];
inline bool which(int x) {
return ch[fa[x]][1] == x;
}
inline bool not_root(int x) {
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
inline void push_up(int x) {
sum[x] = sum[ch[x][0]] ^ sum[ch[x][1]] ^ val[x];
}
inline void reverse(int x) {
swap(ch[x][0], ch[x][1]), rev[x] ^= 1;
}
inline void push_down(int x) {
if (rev[x]) {
rev[x] = 0;
if (ch[x][0])
reverse(ch[x][0]);
if (ch[x][1])
reverse(ch[x][1]);
}
}
inline void rotate(int x) {
int f = fa[x], gf = fa[f], w = which(x), y = ch[x][w^1];
if (not_root(f))
ch[gf][which(f)] = x;
ch[x][w^1] = f, ch[f][w] = y;
if (y)
fa[y] = f;
fa[f] = x, fa[x] = gf;
push_up(f);
}
inline void splay(int x) {
int top = 0, f = x;
stk[++top] = x;
while (not_root(f))
stk[++top] = f = fa[f];
while (top)
push_down(stk[top--]);
while (not_root(x)) {
f = fa[x];
if (not_root(f))
which(x) == which(f) ? rotate(f) : rotate(x);
rotate(x);
}
push_up(x);
}
inline void access(int x) {
for (int y = 0; x; y = x, x = fa[x])
splay(x), ch[x][1] = y, push_up(x);
}
inline void make_root(int x) {
access(x), splay(x), reverse(x);
}
inline int find_root(int x) {
access(x), splay(x);
while (ch[x][0])
push_down(x), x = ch[x][0];
splay(x);
return x;
}
inline void split(int x, int y) {
make_root(x), access(y), splay(y);
}
inline void link(int x, int y) {
make_root(x);
if (find_root(y) != x)
fa[x] = y;
}
inline void cut(int x, int y) {
make_root(x);
if (find_root(y) == x && fa[y] == x && !ch[y][0])
fa[y] = ch[x][1] = 0, push_up(x);
}
} lct;
|