【bz2002】弹飞绵羊

题意：

给出n个节点 及其父亲 和m个指令1：表示求节点i到根节点（n+1）的距离2：表示将节点i的父亲更换为j

题解：

动态树link、cut、access模板题 貌似没什么难度- -

代码：

 #include <cstdio>

 struct info{

        int fat,root,lc,rc,num;

        info(const int a=,const int b=,const int c=,const int d=,const int e=):

                   fat(a),root(b),lc(c),rc(d),num(e){}

 };

 int n,m;

 info tree[];

 void clean(){

      tree[]=info(,,,,);

 }

 void makenum(int t){

      tree[t].num=+tree[tree[t].lc].num+tree[tree[t].rc].num;

 }

 void left(int t){

      int fa=tree[t].fat,r=tree[t].rc;

      tree[t].rc=tree[r].lc;

      tree[tree[r].lc].fat=t;

      tree[r].lc=t;

      tree[t].fat=r;

      if (tree[t].root){

                        tree[t].root=;

                        tree[r].root=;

      }else if (tree[fa].lc==t) tree[fa].lc=r;

      else tree[fa].rc=r;

      tree[r].fat=fa;

      clean();

      makenum(t);

      makenum(r);

 }

 void right(int t){

      int fa=tree[t].fat,l=tree[t].lc;

      tree[t].lc=tree[l].rc;

      tree[tree[l].rc].fat=t;

      tree[l].rc=t;

      tree[t].fat=l;

      if (tree[t].root){

                        tree[t].root=;

                        tree[l].root=;

      }else if (tree[fa].lc==t) tree[fa].lc=l;

            else tree[fa].rc=l;

      tree[l].fat=fa;

      clean();

      makenum(t);

      makenum(l);

 }

 void splay(int t){

      while (!tree[t].root){

            int fa=tree[t].fat,gr=tree[fa].fat;

            if (tree[fa].root){

                               if (tree[fa].lc==t) right(fa);

                               else left(fa);

            }else if (tree[gr].lc==fa){

                     if (tree[fa].lc==t) right(gr),right(fa);

                     else left(fa),right(gr);

                  }else if (tree[fa].rc==t) left(gr),left(fa);

                        else right(fa),left(gr);

      }

 }

 void access(int x){

      int y=x;

      x=;

      do{

          splay(y);

          tree[tree[y].rc].root=;

          tree[y].rc=x;

          tree[x].root=;

          clean();

          makenum(y);

          x=y;

          y=tree[x].fat;

      }while (y);

 }

 void change(int x,int y){

      access(x);

      splay(x);

      tree[tree[x].lc].fat=;

      tree[tree[x].lc].root=;

      tree[x].lc=;

      tree[x].fat=y;

      clean();

      access(x);

 }

 int main(){

     freopen("bz2002.in","r",stdin);

     freopen("bz2002.out","w",stdout);

     int i,x,y,z;

     scanf("%d\n",&n);

     for (i=;i<=n;i++){

         scanf("%d",&x);

         x+=i;

         if (x<=n) tree[i].fat=x;

         else tree[i].fat=n+;

     }

     scanf("%d\n",&m);

     for (i=;i<=m;i++){

         scanf("%d%d",&x,&y);

         ++y;

         if (x==){

                   scanf("%d",&z);

                   change(y,y+z);

         }else{

               access(y);

               splay(y);

               printf("%d\n",tree[tree[y].lc].num);

         }

     }

     fclose(stdin);

     fclose(stdout);

 }