题目大意：有一些洞穴，现在都是彼此分开的，将会被一些无向边所连接。给一些操作，加边，删边，求在某状态下两点之间的联通状态。

思路：简单的Link-Cut-Tree维护图的联通性。基础题，建议初学者刷这个。（我才不会说我被坑第一道题刷的2631。。自己调了2天，然后让同学看2分钟就看出错误了。。。。。。要搞好基础啊！！！）

判断两点是否联通的时候只要暴力找根比较看看一不一样就可以了，不会超时。

CODE：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define MAX 200010 using namespace std; struct Complex{ bool reverse; Complex *son[2],*father; Complex(); bool Check() { return father->son[1] == this; } void Reverse() { reverse ^= 1; swap(son[0],son[1]); } void PushDown() { if(reverse) { son[0]->Reverse(); son[1]->Reverse(); reverse = false; } } }*tree[MAX],*nil = new Complex(); int points,asks; char c[10]; inline void Splay(Complex *a); inline void Rotate(Complex *a,bool dir); inline void Access(Complex *a); inline void ToRoot(Complex *a); inline void Link(Complex *x,Complex *y); inline void Cut(Complex *x,Complex *y); inline void PushPath(Complex *a); bool Ask(Complex *x,Complex *y); int main() { cin >> points >> asks; for(int i = 1;i <= points; ++i) tree[i] = new Complex(); for(int x,y,i = 1;i <= asks; ++i) { scanf("%s%d%d",c,&x,&y); if(c[0] == 'Q') printf("%s\n",Ask(tree[x],tree[y]) ? "Yes":"No"); else if(c[0] == 'C') Link(tree[x],tree[y]); else Cut(tree[x],tree[y]); } return 0; } Complex:: Complex() { father = son[0] = son[1] = nil; reverse = false; } inline void Splay(Complex *a) { PushPath(a); while(a == a->father->son[0] || a == a->father->son[1]) { Complex *p = a->father->father; if(p->son[0] != a->father && p->son[1] != a->father) Rotate(a,!a->Check()); else if(!a->father->Check()) { if(!a->Check()) Rotate(a->father,true),Rotate(a,true); else Rotate(a,false),Rotate(a,true); } else { if(a->Check()) Rotate(a->father,false),Rotate(a,false); else Rotate(a,true),Rotate(a,false); } } } inline void Rotate(Complex *a,bool dir) { Complex *f = a->father; f->son[!dir] = a->son[dir]; f->son[!dir]->father = f; a->son[dir] = f; a->father = f->father; if(f->father->son[0] == f || f->father->son[1] == f) f->father->son[f->Check()] = a; f->father = a; } inline void Access(Complex *a) { Complex *last = nil; while(a != nil) { Splay(a); a->son[1] = last; last = a; a = a->father; } } inline void ToRoot(Complex *a) { Access(a); Splay(a); a->Reverse(); } inline void Link(Complex *x,Complex *y) { ToRoot(x); x->father = y; } inline void Cut(Complex *x,Complex *y) { ToRoot(x); Access(y); Splay(y); x->father = nil; y->son[0] = nil; } inline void PushPath(Complex *a) { static Complex *stack[MAX]; int top = 0; for(;a->father->son[0] == a || a->father->son[1] == a;a = a->father) stack[++top] = a; stack[++top] = a; while(top) stack[top--]->PushDown(); } inline bool Ask(Complex *x,Complex *y) { while(x->father != nil) x = x->father; while(y->father != nil) y = y->father; return x == y; }