1. 题目

传送门=￣ω￣=

2. 题解

Link-Cut-Tree 的模板题啊……(听说还可以用其他的方法做，不管了，直接上 LCT)

没有要求维护点权，只需要维护点的连通性即可。

就是朴素的 LCT，居然还不要 pushup。

感觉有些不适应啊……. 不得不说 LCT 是个神器。

简单分析一下。

• 对于每种命令:
  • 如果是 Connect x y (链接 x y): 直接 link(x,y)即可。
  • 如果是 Destroy x y (切断 x y): 直接 cut(x,y)即可。
  • 如果是 Query x y (询问 x y 的连通性): 判断 findroot(x)和 findroot(y)是否一致，一致输出 Yes，否则输出 No。

然后就 A 了。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define A printf("A")
#define C printf(" ") 
using namespace std;
const int N=2e5+2;
template <typename Tp> inline void IN(Tp &x){
    int f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=f;
}int n,m,f[N],r[N],hep[N],ch[N][2];
inline int chk(int x){return ch[f[x]][1]==x;}
inline int get(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
inline void filp(int x){swap(ch[x][0],ch[x][1]);r[x]^=1;} 
inline void pushdown(int x){
    if(!r[x])return;r[x]=0;
    if(ch[x][0])filp(ch[x][0]);
    if(ch[x][1])filp(ch[x][1]);
}
inline void rotate(int x){
    int y=f[x],z=f[y],k=chk(x),&v=ch[x][!k];
    if(get(y))ch[z][chk(y)]=x;v=y,ch[y][k]=v;
    if(v)f[v]=y;f[y]=x,f[x]=z;return;
}
inline void Splay(int x){
    int y=x,top=0;hep[++top]=y;
    while(get(y))hep[++top]=y=f[y];
    while(top)pushdown(hep[top--]);
    while(get(x)){
        y=f[x],top=f[y];
        if(get(y))rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
        rotate(x);
    }return;
} 
inline void Access(int x){
    for(register int y=0;x;x=f[y=x])
       Splay(x),ch[x][1]=y;
}
inline void makeroot(int x){
    Access(x);Splay(x);filp(x);
}
inline int findroot(int x){
    Access(x);Splay(x);
    while(ch[x][0])pushdown(x),x=ch[x][0];
    return x;
}
inline void split(int x,int y){
    makeroot(x);Access(y);Splay(y);
} 
inline void link(int x,int y){
    makeroot(x);if(findroot(y)!=x)f[x]=y;
}
inline void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&f[x]==y&&!ch[x][1]){
        f[x]=ch[y][0]=0;
    }return;
}char op[10];
int main(){
    scanf("%d%d",&n,&m);
    for(register int x,y,i=1;i<=m;++i){
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='C')link(x,y);
        else if(op[0]=='D')cut(x,y);
        else if(op[0]=='Q'){
            if(findroot(x)==findroot(y))printf("Yes\n");
            else printf("No\n");
        }   
    }return 0;
}