【bzoj2049】[Sdoi2008]Cave 洞穴勘测 link-cut-tree

#include<bits/stdc++.h>
#define N 10005
#define inf 1000000000
#define ll long long
using namespace std;
int read(){
  int x=0,f=1;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();}
  return x*f;
}
namespace LCT{
  int ch[N][2],fa[N];bool rev[N];
  inline bool isroot(int x){
    if(ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)return 1;return 0;
  }
  inline void pushdown(int x){
    if(rev[x]){
      rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]=0;
      swap(ch[x][0],ch[x][1]);
    }
  }
  void Pushdown(int x){
    if(!isroot(x))Pushdown(fa[x]);//splay中是否是根 
    pushdown(x);
  }
  void rotate(int x){
      int y=fa[x],k=ch[y][1]==x;
      if(!isroot(y))ch[fa[y]][ch[fa[y]][1]==y]=x;
      fa[x]=fa[y];
      fa[y]=x;
      fa[ch[x][!k]]=y;
      ch[y][k]=ch[x][!k];
      ch[x][!k]=y;
  }
  void splay(int x){
      Pushdown(x);
      for(int y=fa[x];!isroot(x);y=fa[x]){
        if(!isroot(y)){
            if((ch[fa[y]][1]==y)!=(ch[y][1]==x))rotate(x);
            else rotate(y);
        }rotate(x);
    }
  }
  inline void access(int x){
    int y=0;
    while(x){
      splay(x);
      ch[x][1]=y;
      x=fa[y=x];
    }
  }
  inline void moveroot(int x){
    access(x);splay(x);rev[x]^=1;
  }
  inline void link(int x,int y){
      moveroot(x);fa[x]=y;splay(x);
  }
  inline void cut(int x,int y){
      moveroot(x);access(y);splay(y);ch[y][0]=fa[x]=0;
  }
  inline int find(int x){
    access(x);splay(x);
    while(ch[x][0]){
      x=ch[x][0];
      pushdown(x);
    }
    return x;
  }
}
int n,m;
char ch[10];
int main(){
  n=read();m=read();
  while(m--){
    scanf("%s",ch);
    int x=read(),y=read();
    if(ch[0]==‘C‘)LCT::link(x,y);
    else if(ch[0]==‘D‘)LCT::cut(x,y);
    else if(LCT::find(x)==LCT::find(y))printf("Yes\n");else printf("No\n");
  }
  return 0;
}