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
| #include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=getchar(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
const int MAXN=1e4+10;
int N,Q;
struct LCT
{
int chi[2],fa,rev;
}Tr[MAXN];
#define ls(p) Tr[p].chi[0]
#define rs(p) Tr[p].chi[1]
inline void pushRev(int p)
{
std::swap(ls(p),rs(p));
Tr[p].rev^=1;
}
inline void pushDown(int p)
{
if(Tr[p].rev)
{
pushRev(ls(p)),pushRev(rs(p));
Tr[p].rev=0;
}
}
inline bool isRoot(int x)
{
return (ls(Tr[x].fa)!=x&&rs(Tr[x].fa)!=x);
}
inline void rotate(int x)
{
int y=Tr[x].fa,z=Tr[y].fa;
int k=rs(y)==x;
if(!isRoot(y)) Tr[z].chi[rs(z)==y]=x;
Tr[x].fa=z;
Tr[y].chi[k]=Tr[x].chi[k^1],Tr[Tr[x].chi[k^1]].fa=y;
Tr[x].chi[k^1]=y,Tr[y].fa=x;
}
inline void Splay(int x)
{
int r=x,Top=0;
static int Stk[MAXN];
Stk[++Top]=r;
while(!isRoot(r)) Stk[++Top]=r=Tr[r].fa;
while(Top) pushDown(Stk[Top--]);
while(!isRoot(x))
{
int y=Tr[x].fa,z=Tr[y].fa;
if(!isRoot(y))
if((rs(y)==x)^(rs(z)==y)) rotate(x);
else rotate(y);
rotate(x);
}
}
inline void access(int x)
{
int z=x;
for(int y=0;x;y=x,x=Tr[x].fa)
{
Splay(x);
rs(x)=y;
}
Splay(z);
}
inline void makeRoot(int x)
{
access(x);
pushRev(x);
}
inline int findRoot(int x)
{
access(x);
while(ls(x)) pushDown(x),x=ls(x);
return Splay(x),x;
}
inline void link(int x,int y)
{
makeRoot(x);
if(findRoot(y)!=x) Tr[x].fa=y;
}
inline void cut(int x,int y)
{
makeRoot(x);
if(findRoot(y)==x&&Tr[y].fa==x&&!ls(y)) rs(x)=Tr[y].fa=0;
}
inline bool edge(int x,int y)
{
return (findRoot(x)==findRoot(y));
}
char opt[20];
int main()
{
read(N,Q);
for(int u,v;Q--;)
{
scanf("%s",opt),read(u,v);
if(opt[0]=='Q') puts(edge(u,v)?"Yes":"No");
else if(opt[0]=='C') link(u,v);
else if(opt[0]=='D') cut(u,v);
}
return 0;
}
|