传送门
这是笔者第一次写lct。
这题操作比较少，就当是练习压行技巧了吧。
然后学习lct时一定记住把原树和辅助树区别开来。
代码：
#include<bits/stdc++.h>
#define N 10005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int son[N][2],fa[N],rev[N],stk[N],top,n,m;
inline int which(int x){return x==son[fa[x]][1];}
inline bool isroot(int x){return !fa[x]||(x!=son[fa[x]][0]&&x!=son[fa[x]][1]);}
inline void pushdown(int x){
if(rev[x]){
swap(son[x][0],son[x][1]);
if(son[x][0])rev[son[x][0]]^=1;
if(son[x][1])rev[son[x][1]]^=1;
rev[x]^=1;
}
}
inline void rotate(int x){
int y=fa[x],z=fa[y],t=which(x);
if(z&&!isroot(y))son[z][which(y)]=x;
fa[y]=x,fa[x]=z,son[y][t]=son[x][t^1],son[x][t^1]=y;
if(son[y][t])fa[son[y][t]]=y;
}
inline void splay(int x){
stk[top=1]=x;
for(int i=x;!isroot(i);i=fa[i])stk[++top]=fa[i];
while(top)pushdown(stk[top]),--top;
while(!isroot(x)){if(!isroot(fa[x]))rotate(which(x)==which(fa[x])?fa[x]:x);rotate(x);}
}
inline void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),son[x][1]=y;}
inline int findroot(int x){
access(x),splay(x);
while(pushdown(x),son[x][0])x=son[x][0];
return splay(x),x;
}
inline void makeroot(int x){access(x),splay(x),rev[x]^=1;}
inline void link(int a,int b){makeroot(a),fa[a]=b;}
inline void cut(int a,int b){makeroot(a),access(b),splay(b),son[b][0]=fa[a]=0;}
int main(){
n=read(),m=read();
for(int i=1;i<=m;++i){
char s[10];
int a,b;
scanf("%s",s),a=read(),b=read();
if(s[0]=='C')link(a,b);
else if(s[0]=='D')cut(a,b);
else puts(findroot(a)==findroot(b)?"Yes":"No");
}
return 0;
}