洛谷P2147 [SDOI2008]Cave 洞穴勘测 Link-Cut Tree LCT

洛谷P2147 [SDOI2008]Cave 洞穴勘测
Link-Cut Tree LCT
第一次做LCT的题目，就当先挖个坑吧。
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <cstdlib>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iomanip>
  8 #include <iostream>
  9 #define N 10010 
 10 #define read(a) a=getnum()
 11 using namespace std ;
 12 
 13 inline int getnum() 
 14 { int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar()); 
 15 for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; } 
 16 int n,m,x,y,f[N],ch[N][2],siz[N],res[N] ;
 17 char s[10] ;
 18 void update(int x) 
 19 {
 20     siz[x] = 1+siz[ch[x][0]] + siz[ch[x][1]] ;
 21 }
 22 
 23 void pushdown(int x) 
 24 
 25 {
 26     if(res[x]&&x) 
 27     {
 28         if(ch[x][0]) res[ch[x][0]]^=1 ;
 29         if(ch[x][1]) res[ch[x][1]]^=1 ;
 30         swap(ch[x][1],ch[x][0]) ;
 31         res[x] = 0 ;
 32     }
 33 }
 34 
 35 int is_root(int x) 
 36 {
 37     return ch[f[x]][1]!=x &&ch[f[x]][0] != x;
 38 }
 39 
 40 int get_son(int x ) 
 41 {
 42     return ch[f[x]][1] == x;   //返回  当前的节点是左儿子还是右儿子 
 43 }
 44 
 45 void rot(int x) 
 46 {
 47     int fa = f[x],fafa = f[fa] , k = get_son(x) ;
 48     if(!is_root(fa)) 
 49         ch[fafa][ch[fafa][1]==fa] = x ;
 50     ch[fa][k] = ch[x][k^1],f[ch[fa][k]] = fa ; 
 51     ch[x][k^1] = fa,f[fa] = x ;
 52     f[x] = fafa ;
 53     update(fa) ;
 54     update(x) ;
 55 }
 56 
 57 void push(int x) 
 58 {
 59     if(!is_root(x)) push(f[x]) ;
 60     pushdown(x) ;
 61 }
 62 
 63 void splay(int x)     //  splay   到当前辅助树的顶   
 64 {
 65     push(x) ;
 66     for(int fa;!is_root(x);rot(x)) 
 67         if(!is_root(fa=f[x])) 
 68             rot(get_son(x)==get_son(fa)?fa:x) ;
 69 }
 70 
 71 void access(int x)    //  一直向上 splay  直到到 原树的顶 
 72 {
 73     for(int y=0;x;y=x,x=f[x]) 
 74          splay(x),ch[x][1] = y ; 
 75 }
 76 
 77 int find_root(int x) 
 78 {
 79     access(x),splay(x) ;
 80     while(ch[x][0]) 
 81          x = ch[x][0] ;
 82     return x ;
 83 }
 84 
 85 void make_root(int x) 
 86 {
 87     access(x);splay(x);res[x]^=1 ;     //  翻转 
 88 }
 89 
 90 void link(int x,int y ) 
 91 {
 92     make_root(x),f[x] = y ; splay(x) ;
 93 }
 94 
 95 void cut(int x,int y) 
 96 {
 97     make_root(x),access(y),splay(y),ch[y][0] = f[x] = 0 ;   //  x一定是y的左儿子 
 98 }
 99 
100 int main()
101 {
102     read(n);read(m) ;
103     for(int i=1;i<=m;i++) 
104     {
105         scanf("%s",&s) ;
106         read(x);read(y) ;
107         if(s[0]=='Q') 
108             if(find_root(x)==find_root(y)) 
109                 printf("Yes
") ;
110             else printf("No
") ;
111         if(s[0]=='C') 
112              link(x,y) ;
113         if(s[0]=='D') 
114             cut(x,y) ;
115     }
116     return 0 ;
117 }