熟练剖分

路径到根直接向上跳

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN=101111;int N, M;int P;string com;struct Vert{    int Fa, Son, Bro;    int Size, Dep;    int MainSon, Top;    int Dps, Dpr;} V[MAXN];void DFS1(int at){    V[at].Size=1;    for(int to=V[at].Son;to>0;to=V[to].Bro){        V[to].Dep=V[at].Dep+1;        DFS1(to);        V[at].Size+=V[to].Size;        if(V[at].MainSon<=0 || V[to].Size>V[V[at].MainSon].Size)    V[at].MainSon=to;    }}int Dfn[MAXN], DFN;void DFS2(int at, int t){    ++DFN;    Dfn[DFN]=at;V[at].Dps=DFN;    V[at].Top=t;    if(V[at].MainSon>0) DFS2(V[at].MainSon, t);    for(int to=V[at].Son;to>0;to=V[to].Bro){        if(to==V[at].MainSon)   continue;        DFS2(to, to);    }    V[at].Dpr=DFN;/**/}struct Node{    int l, r;    int Sum;    int opt;} T[MAXN<<2];int L, R, op;int Sum;void BuildTree(int l, int r, int at){    T[at].l=l;T[at].r=r;T[at].Sum=0;T[at].opt=-1;    if(l
       
        >1;        BuildTree(l, m, at<<1);        BuildTree(m+1, r, (at<<1)|1);    }}void opr(int at){    T[at].Sum=op*(T[at].r-T[at].l+1);}void cop(int at){    T[at].opt=op;}void pdw(int at){    if(T[at].opt==-1)   return;    int top=op;op=T[at].opt;    opr(at<<1);cop(at<<1);    opr((at<<1)|1);cop((at<<1)|1);    op=top;T[at].opt=-1;}void pup(int at){    T[at].Sum=T[at<<1].Sum+T[(at<<1)|1].Sum;}int Ask(int at){    if(T[at].l>=L && T[at].r<=R){        return T[at].Sum;    }    pdw(at);    int m=(T[at].l+T[at].r)>>1;    int ret=0;    if(L<=m)    ret+=Ask(at<<1);    if(R>m) ret+=Ask((at<<1)|1);    return ret;}void Update(int at){    if(T[at].l>=L && T[at].r<=R){        T[at].Sum=op*(T[at].r-T[at].l+1);        T[at].opt=op;        return;    }    pdw(at);    int m=(T[at].l+T[at].r)>>1;    if(L<=m)    Update(at<<1);    if(R>m) Update((at<<1)|1);    pup(at);}int main(){    ios_base::sync_with_stdio(false);        cin >> N;    for(int i=2, f;i<=N;++i){        cin >> f;++f;        V[i].Fa=f;V[i].Bro=V[f].Son;V[f].Son=i;    }        V[1].Dep=1;    DFS1(1);    DFS2(1, 1);        assert(DFN==N);    BuildTree(1, N, 1);        cin >> M;    while(M--){        cin >> com >> P;++P;        Sum=0;        if(com[0]=='i'){            op=1;            for(int k=P;k>0;k=V[V[k].Top].Fa){                L=V[V[k].Top].Dps;R=V[k].Dps;                Sum+=Ask(1);                Update(1);            }            cout << V[P].Dep-Sum << endl;        }        else{            op=0;            L=V[P].Dps;R=V[P].Dpr;            Sum=Ask(1);            Update(1);            cout << Sum << endl;        }    }        return 0;}