省选前集训 lca

LCA
描述
加边，删边，动态求两点的lca
删边以后要恢复以前的跟，因为lca与树根有关，不能随意旋转树
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define maxn 100020
  7 
  8 int fa[maxn],child[maxn][2],rev[maxn];
  9 int n,m;
 10 int stack[maxn],tops = -1;
 11 
 12 inline bool isroot(int x){
 13     return (child[fa[x]][0] != x && child[fa[x]][1] != x);
 14 }
 15 inline void reverse(int x){
 16     rev[x] ^= 1;
 17     swap(child[x][0],child[x][1]);
 18 }
 19 inline void pushdown(int x){
 20     if ( rev[x] ) {
 21         if ( child[x][0] ) reverse(child[x][0]);
 22         if ( child[x][1] ) reverse(child[x][1]);
 23         rev[x] = 0;
 24     }
 25 }
 26 inline void rotate(int x){
 27     int t = child[fa[x]][1] == x;
 28     int y = fa[x] , z = child[x][1 - t];
 29     fa[x] = fa[y];
 30     if ( !isroot(y) ) child[fa[x]][child[fa[x]][1] == y] = x;
 31     fa[y] = x;
 32     child[x][1 - t] = y;
 33     if ( z ){
 34         fa[z] = y;
 35     }
 36     child[y][t] = z;
 37 }
 38 inline void splay(int x){
 39     stack[++tops] = x;
 40     for (int i = x ; !isroot(i) ; i = fa[i]) stack[++tops] = fa[i]; 
 41     while ( ~tops ) pushdown(stack[tops--]);
 42     while ( !isroot(x) ){
 43         int y = fa[x] , z = fa[y];
 44         if ( (!((child[z][0] == y) ^ (child[y][0] == x))) && !isroot(y) ) rotate(y);
 45         else rotate(x);
 46         if ( isroot(x) ) break;
 47         rotate(x);    
 48     }
 49 }
 50 inline int access(int x){
 51     int t = 0;
 52     for (;x;x = fa[x])
 53         splay(x) , child[x][1] = t , t = x;
 54     return t;
 55 }
 56 inline void makeroot(int x){
 57     access(x);
 58     splay(x);
 59     reverse(x);
 60 }
 61 inline void link(int x,int y){
 62     makeroot(y);
 63     fa[y] = x;
 64 }
 65 inline int findroot(int x){
 66     access(x);
 67     splay(x);
 68     pushdown(x);
 69     while ( child[x][0] ) x = child[x][0] , pushdown(x);
 70     return x;
 71 }
 72 inline void cut(int x,int y){
 73     int R = findroot(x);
 74     makeroot(y);
 75     access(x);
 76     splay(x);
 77     child[x][0] = fa[y] = 0;
 78     makeroot(R);
 79 }
 80 inline int getans(int x,int y){
 81     if ( findroot(x) != findroot(y) ) return -1;
 82     access(x);
 83     return access(y);
 84 }    
 85 void print(){
 86     for (int i = 1 ; i <= n ; i++) cout<<i<<" fa "<<fa[i]<<" child "<<child[i][0]<<" "<<child[i][1]<<endl;
 87 }
 88 int main(){
 89     freopen("lca.in","r",stdin);
 90     freopen("lca.out","w",stdout);
 91     scanf("%d %d",&n,&m);
 92     for (int i = 1 ; i <= m ; i++){
 93         int t,x,y;
 94         scanf("%d %d %d",&t,&x,&y);
 95         if ( t == 1 ) link(x,y);
 96         else if ( t == 2 ){
 97             if ( fa[x] == y ) cut(x,y);
 98             else cut(y,x);
 99         }
100         else printf("%d
",getans(x,y));
101     //    cout<<i<<endl;
102     //    print();
103     }    
104     return 0;
105 }