BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊（动态树）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2002

【题目大意】

　　给出一片森林，操作允许更改一个节点的父亲，查询一个节点的深度。

【题解】

　　更改父亲操作直接cutf然后修改一下即可，查询深度则直接提取链然后splay一下

【代码】

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=200010;

int f[N],son[N][2],val[N],sum[N],tmp[N];bool rev[N];

bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}

void rev1(int x){if(!x)return;swap(son[x][0],son[x][1]);rev[x]^=1;}

void pb(int x){if(rev[x])rev1(son[x][0]),rev1(son[x][1]),rev[x]=0;}

void up(int x){

    sum[x]=val[x];

    if(son[x][0])sum[x]+=sum[son[x][0]];

    if(son[x][1])sum[x]+=sum[son[x][1]];

}

void rotate(int x){

    int y=f[x],w=son[y][1]==x;

    son[y][w]=son[x][w^1];

    if(son[x][w^1])f[son[x][w^1]]=y;

    if(f[y]){

        int z=f[y];

        if(son[z][0]==y)son[z][0]=x;else if(son[z][1]==y)son[z][1]=x;

    }f[x]=f[y];f[y]=x;son[x][w^1]=y;up(y);

}

void splay(int x){

    int s=1,i=x,y;tmp[1]=i;

    while(!isroot(i))tmp[++s]=i=f[i];

    while(s)pb(tmp[s--]);

    while(!isroot(x)){

        y=f[x];

        if(!isroot(y)){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}

        rotate(x);

    }up(x);

}

void access(int x){for(int y=0;x;y=x,x=f[x])splay(x),son[x][1]=y,up(x);}

void cutf(int x){access(x);splay(x);f[son[x][0]]=0;son[x][0]=0;up(x);}

int query(int x){access(x);splay(x);return sum[x];}

int n,x,y,q,op,K[N];

int main(){

    scanf("%d",&n);

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

        scanf("%d",&K[i]);

        if(i+K[i]>n)f[i]=0;

        else f[i]=i+K[i];

        val[i]=sum[i]=1;

    }scanf("%d",&q);

    while(q--){

        scanf("%d%d",&op,&x);x++;

        if(op==1)printf("%d\n",query(x));

        else{

            scanf("%d",&y);

            if(x+y>n)y=0; else y=x+y;

            K[x]=y; cutf(x); f[x]=y;

        }

    }return 0;

}