【bz2002】弹飞绵羊

题意：
给出n个节点及其父亲和m个指令1：表示求节点i到根节点（n+1）的距离2：表示将节点i的父亲更换为j
题解：
动态树link、cut、access模板题貌似没什么难度- -
代码：
  1 #include <cstdio>
  2 struct info{
  3        int fat,root,lc,rc,num;
  4        info(const int a=0,const int b=1,const int c=0,const int d=0,const int e=1):
  5                   fat(a),root(b),lc(c),rc(d),num(e){}
  6 };
  7 int n,m;
  8 info tree[200002];
  9 void clean(){
 10      tree[0]=info(0,0,0,0,0);
 11 }
 12 void makenum(int t){
 13      tree[t].num=1+tree[tree[t].lc].num+tree[tree[t].rc].num;
 14 }
 15 void left(int t){
 16      int fa=tree[t].fat,r=tree[t].rc;
 17      tree[t].rc=tree[r].lc;
 18      tree[tree[r].lc].fat=t;
 19      tree[r].lc=t;
 20      tree[t].fat=r;
 21      if (tree[t].root){
 22                        tree[t].root=0;
 23                        tree[r].root=1;
 24      }else if (tree[fa].lc==t) tree[fa].lc=r;
 25      else tree[fa].rc=r;
 26      tree[r].fat=fa;
 27      clean();
 28      makenum(t);
 29      makenum(r);
 30 }
 31 void right(int t){
 32      int fa=tree[t].fat,l=tree[t].lc;
 33      tree[t].lc=tree[l].rc;
 34      tree[tree[l].rc].fat=t;
 35      tree[l].rc=t;
 36      tree[t].fat=l;
 37      if (tree[t].root){
 38                        tree[t].root=0;
 39                        tree[l].root=1;
 40      }else if (tree[fa].lc==t) tree[fa].lc=l;
 41            else tree[fa].rc=l;
 42      tree[l].fat=fa;
 43      clean();
 44      makenum(t);
 45      makenum(l);
 46 }
 47 void splay(int t){
 48      while (!tree[t].root){
 49            int fa=tree[t].fat,gr=tree[fa].fat;
 50            if (tree[fa].root){
 51                               if (tree[fa].lc==t) right(fa);
 52                               else left(fa);
 53            }else if (tree[gr].lc==fa){
 54                     if (tree[fa].lc==t) right(gr),right(fa);
 55                     else left(fa),right(gr);
 56                  }else if (tree[fa].rc==t) left(gr),left(fa);
 57                        else right(fa),left(gr);
 58      }
 59 }
 60 void access(int x){
 61      int y=x;
 62      x=0;
 63      do{
 64          splay(y);
 65          tree[tree[y].rc].root=1;
 66          tree[y].rc=x;
 67          tree[x].root=0;
 68          clean();
 69          makenum(y);
 70          x=y;
 71          y=tree[x].fat;
 72      }while (y);
 73 }
 74 void change(int x,int y){
 75      access(x);
 76      splay(x);
 77      tree[tree[x].lc].fat=0;
 78      tree[tree[x].lc].root=1;
 79      tree[x].lc=0;
 80      tree[x].fat=y;
 81      clean();
 82      access(x);
 83 }
 84 int main(){
 85     freopen("bz2002.in","r",stdin);
 86     freopen("bz2002.out","w",stdout);
 87     int i,x,y,z;
 88     scanf("%d
",&n);
 89     for (i=1;i<=n;i++){
 90         scanf("%d",&x);
 91         x+=i;
 92         if (x<=n) tree[i].fat=x;
 93         else tree[i].fat=n+1;
 94     }
 95     scanf("%d
",&m);
 96     for (i=1;i<=m;i++){
 97         scanf("%d%d",&x,&y);
 98         ++y;
 99         if (x==2){
100                   scanf("%d",&z);
101                   change(y,y+z);
102         }else{
103               access(y);
104               splay(y);
105               printf("%d
",tree[tree[y].lc].num);
106         }
107     }
108     fclose(stdin);
109     fclose(stdout);
110 }
View Code