[bzoj2049][SDOI2008]Cave 洞穴勘测

题目链接

比LCT板子还板子的板子题。


Code

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
#include <cstdio>
#include <cstring>
#include <cctype>
#define N 10005
int n,m,val[N];
struct link_cut_tree
{
int top,c[N][2],fa[N],s[N],st[N],rev[N];
inline void pushup(int x){s[x] = s[c[x][0]] ^ s[c[x][1]] ^ val[x];}
inline void pushdown(int x)
{
int l = c[x][0],r = c[x][1];
if(rev[x])
{
rev[x] ^= 1;rev[l] ^= 1;rev[r] ^= 1;
std::swap(c[x][0],c[x][1]);
}
}
inline bool isroot(int x){return c[fa[x]][0] != x && c[fa[x]][1] != x;}
void rotate(int x)
{
int y = fa[x],z = fa[y],l,r;
if(c[y][0] == x) l = 0;else l = 1;r = l ^ 1;
if(!isroot(y)){if(c[z][0] == y) c[z][0] = x;else c[z][1] = x;}
fa[x] = z;fa[y] = x;fa[c[x][r]] = y;
c[y][l] = c[x][r];c[x][r] = y;
pushup(y);pushup(x);
}
void splay(int x)
{
top = 1;st[top] = x;
for(int i = x;!isroot(i);i = fa[i]) st[++top] = fa[i];
for(int i = top;i;i--) pushdown(st[i]);
while(!isroot(x))
{
int y = fa[x],z = fa[y];
if(!isroot[y])
{
if((c[y][0] == x) ^ (c[z][0] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){for(int t = 0;x;t = x,x = fa[x]) splay(x),c[x][1] = t,pushup(x);}
void makeroot(int x){access(x);splay(x);rev[x] ^= 1;}
int find(int x){access(x);splay(x);while(c[x][0])x = c[x][0];return x;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void cut(int x,int y){split(x,y);if(c[y][0] == x)c[y][0] = fa[x] = 0;}
void link(int x,int y){makeroot(x);fa[x] = y;}
}T;
inline int getint()
{
register int num = 0,sgn = 1;register char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = 0;
for(;isdigit(ch);ch = getchar()) num = (num << 3) + (num << 1) + ch - '0';return sgn ? num : -num;
}
inline char getupper(){register char ch = getchar();while(!isupper(ch))ch = getchar();return ch;}
int main()
{
n = getint();m = getint();
while(m--)
{
char opt = getupper();int x = getint(),y = getint();
switch(opt)
{
case 'C': link(x,y);break;
case 'D': cut(x,y);break;
default: if(find(x) == find(y)) printf("Yes\n"); else printf("No\n");
}
}
return 0;
}