LCT

  1 /**************************************************************  2     Problem: 2049  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:1920 ms  7     Memory:1480 kb  8 ****************************************************************/  9   10 //BZOJ 2049 11 #include<cstdio> 12 #include<cstring> 13 #include<cstdlib> 14 #include<iostream> 15 #include<algorithm> 16 #define rep(i,n) for(int i=0;i<n;++i) 17 #define F(i,j,n) for(int i=j;i<=n;++i) 18 #define D(i,j,n) for(int i=j;i>=n;--i) 19 using namespace std; 20 const int N=10086; 21   22 int c[N][2],fa[N],n,m,st[N<<1],top=0; 23 bool rev[N]; 24   25 void Push_down(int x){ 26     int l=c[x][0],r=c[x][1]; 27     if (rev[x]){ 28         rev[x]^=1; rev[l]^=1; rev[r]^=1; 29         swap(c[x][0],c[x][1]); 30     } 31 } 32   33 bool isroot(int x){ 34     return c[fa[x]][0]!=x && c[fa[x]][1]!=x; 35 } 36   37 void rotate(int x){ 38     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 39     if (!isroot(y)) c[z][c[z][1]==y]=x; 40     fa[x]=z; fa[y]=x; fa[c[x][r]]=y; 41     c[y][l]=c[x][r]; c[x][r]=y; 42 } 43   44 void splay(int x){ 45     top=0; st[top++]=x; 46     for(int y=x;!isroot(y);y=fa[y]) 47         st[top++]=fa[y]; 48     while(top--) Push_down(st[top]); 49       50     while(!isroot(x)){ 51         int y=fa[x],z=fa[y]; 52         if (!isroot(y)){ 53             if(c[y][0]==x^c[z][0]==y) rotate(x); 54             else rotate(y); 55         } 56         rotate(x); 57     } 58 } 59   60 void access(int x){ 61     for(int t=0;x;t=x,x=fa[x]) 62         splay(x),c[x][1]=t; 63 } 64   65 void makeroot(int x){ 66     access(x); splay(x); rev[x]^=1; 67 } 68   69 int find(int x){ 70     access(x); splay(x); 71     while(c[x][0]) x=c[x][0]; 72     return x; 73 } 74   75 void cut(int x,int y){ 76     makeroot(x); 77     access(y); 78     splay(y); 79     if (c[y][0]==x) c[y][0]=fa[x]=0; 80 } 81   82 void link(int x,int y){ 83     makeroot(x); fa[x]=y; 84 } 85 //LCT end   86 int main(){ 87 //  freopen("input.txt","r",stdin); 88     scanf("%d%d",&n,&m); 89     char cmd[10]; 90     int x,y; 91     F(i,1,m){ 92         scanf("%s%d%d",cmd,&x,&y); 93         if (cmd[0]==‘C‘) link(x,y); 94         else if (cmd[0]==‘D‘){ 95             if (find(x)==find(y)) cut(x,y); 96         } 97         else if (cmd[0]==‘Q‘){ 98             if (find(x)==find(y)) printf("Yes\n"); 99             else printf("No\n");100         }101     }102     return 0;103 }