bzoj2002 弹飞绵羊 lct版

这道题就是维护一个有根的lct 一开始建树全部建虚边 求多少次弹出就是求他到根的距离（根为n+1）

这里有个小技巧 将n+1作为根而没有虚根操作起来会比较方便

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,c[M][],size[M],fa[M];

bool isrt(int x){return c[fa[x]][]!=x&&c[fa[x]][]!=x;}

void up(int x){size[x]=size[c[x][]]+size[c[x][]]+;}

void rotate(int x){

    int y=fa[x],z=fa[y],l=,r=;

    if(c[y][]==x) l=,r=;

    if(!isrt(y)) c[z][c[z][]==y]=x;

    fa[y]=x; fa[x]=z; fa[c[x][r]]=y;

    c[y][l]=c[x][r]; c[x][r]=y;

    up(y); up(x);

}

void splay(int x){

    while(!isrt(x)){

        int y=fa[x],z=fa[y];

        if(!isrt(y)){

            if(c[z][]==y^c[y][]==x) rotate(x);

            else rotate(y);

        }

        rotate(x);

    }

}

void acs(int x){

    int t=,y=x;

    while(x){

        splay(x);

        c[x][]=t;

        up(x);

        t=x; x=fa[x];

    }

    splay(y);

}

void cut_link(int x,int y){

    acs(x);

    fa[c[x][]]=; c[x][]=;

    fa[x]=min(y+x,n+);

}

int push_ans(int x){acs(x); return size[x]-;}

int main()

{

    int x,y;

    n=read();

    for(int i=;i<=n+;i++) size[i]=;

    for(int i=;i<=n;i++) y=read(),fa[i]=min(i+y,n+);

    m=read();

    while(m--){

        if(read()==) x=read()+,printf("%d\n",push_ans(x));

        else x=read()+,y=read(),cut_link(x,y);

    }

    return ;

}