题意：维护一个动态并查集，支持加边，删边，维护两点连通性。
主要用到了 lct 的 Access FindRoot ChangeRoot link cut 操作。
#include#include #include #include #include using namespace std;#define maxn 10005int fa[maxn],c[maxn][2],siz[maxn];bool is_root[maxn],delta[maxn];void Mark(int x){ if(x){ delta[x]^=1; }}void Maintain(int x){ siz[x]=siz[c[x][0]]+siz[c[x][1]]+1;}void pushdown(int x){ if(delta[x]){ Mark(c[x][0]); Mark(c[x][1]); swap(c[x][0],c[x][1]); delta[x]=0; }}void Rotate(int x,bool flag){ int y=fa[x]; c[y][!flag]=c[x][flag]; if(c[x][flag]){ fa[c[x][flag]]=y; } if(fa[y] && c[fa[y]][c[fa[y]][1]==y]==y){ c[fa[y]][c[fa[y]][1]==y]=x; } fa[x]=fa[y]; c[x][flag]=y; fa[y]=x; if(is_root[y]){ is_root[y]=0; is_root[x]=1; } Maintain(y); Maintain(x);}stack st;void Splay(int x){ pushdown(x); if(!x || is_root[x]){ return; } int U=x; while(!is_root[U]){ st.push(U); U=fa[U]; } st.push(U); while(!st.empty()){ pushdown(st.top()); st.pop(); } int y; while(y=fa[x],(!is_root[x])){ if(is_root[y]){ Rotate(x,c[y][0]==x); } else{ if((c[y][0]==x)==(c[fa[y]][0]==y)){ Rotate(y,c[fa[y]][0]==y); } else{ Rotate(x,c[y][0]==x); y=fa[x]; } Rotate(x,c[y][0]==x); } } Maintain(x);}void Access(int x){ int y; Splay(x); while(fa[x]){ y=fa[x]; Splay(y); Splay(x); if(c[y][1]){ is_root[c[y][1]]=1; } is_root[x]=0; c[y][1]=x; Splay(x); } if(c[x][1]){ is_root[c[x][1]]=1; c[x][1]=0; }}void ChangeRoot(int x){ Access(x); Splay(x); Mark(x);}void cut(int x){ Access(x); Splay(x); fa[c[x][0]]=0; if(c[x][0]){ is_root[c[x][0]]=1; } c[x][0]=0;}void link(int x,int y){ Access(x); Splay(x);// Mark(c[x][0]); Access(y); Splay(y); c[y][1]=x; fa[x]=y; is_root[x]=0;}int FindRoot(int x){ Access(x); Splay(x); while(c[x][0]){ x=c[x][0]; } return x;}int n,m;int main(){// freopen("bzoj2049.in","r",stdin); char op[10]; int x,y; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ siz[i]=1; is_root[i]=1; } for(int i=1;i<=m;++i){ scanf("%s%d%d",op,&x,&y); if(op[0]=='Q'){ puts(FindRoot(x)==FindRoot(y) ? "Yes" : "No"); } else if(op[0]=='C'){ ChangeRoot(x); link(x,y); } else{ if(FindRoot(x)==FindRoot(y)){ ChangeRoot(x); cut(y); } } } return 0;}