题目：

树链剖分。

代码如下：

#include
     
      #include
      
       #include
       
        using namespace std;int const maxn=1e5+5;int n,m,fa[maxn],dfn[maxn],end[maxn],top[maxn],to[maxn],siz[maxn],head[maxn],ct,tim;struct N{    int to,next;    N(int t=0,int n=0):to(t),next(n) {}}edge[maxn];struct T{
   int sum,siz; bool f[3];}t[maxn<<2];int rd(){    int ret=0;char ch=getchar();    while(ch<'0'||ch>'9')ch=getchar();    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();    return ret;}void dfs(int x){    siz[x]=1;    for(int i=head[x],u;i;i=edge[i].next)    {        dfs(u=edge[i].to);        if(siz[u]>siz[to[x]])to[x]=u;        siz[x]+=siz[u];    }}void dfs2(int x){    dfn[x]=++tim;//不在dfs     if(to[x])top[to[x]]=top[x],dfs2(to[x]);    for(int i=head[x],u;i;i=edge[i].next)    {        if((u=edge[i].to)==to[x])continue;        top[u]=u; dfs2(u);    }    end[x]=tim;}void pushup(int x){    int ls=(x<<1),rs=(x<<1|1);    t[x].siz=t[ls].siz+t[rs].siz;    t[x].sum=t[ls].sum+t[rs].sum;}void pushdown(int x){    if(!t[x].f[0]&&!t[x].f[1])return;    int ls=(x<<1),rs=(x<<1|1);    for(int i=0;i<=1;i++)        if(t[x].f[i])        {            t[x].f[i]=0; t[ls].f[i]=1; t[rs].f[i]=1;            t[ls].f[!i]=0; t[rs].f[!i]=0;            t[ls].sum=t[ls].siz*i; t[rs].sum=t[rs].siz*i;        }}void build(int x,int l,int r){    if(l==r){t[x].siz=1;return;}    int mid=((l+r)>>1);    build(x<<1,l,mid); build(x<<1|1,mid+1,r);    pushup(x);}int query(int x,int l,int r,int L,int R,int val){    if(l>=L&&r<=R)    {        if(val)return t[x].sum;        else return t[x].siz-t[x].sum;    }    int mid=((l+r)>>1),ret=0;    pushdown(x);    if(mid>=L)ret+=query(x<<1,l,mid,L,R,val);    if(mid
        
         <<1|1,mid+1,r,L,R,val);    return ret;}void update(int x,int l,int r,int L,int R,int val){    if(l>=L&&r<=R)    {        t[x].f[val]=1;  t[x].f[!val]=0;        t[x].sum=t[x].siz*val; return;    }    int mid=((l+r)>>1);    if(mid>=L)update(x<<1,l,mid,L,R,val);    if(mid
         
          <<1|1,mid+1,r,L,R,val);    pushup(x);}int ask(int x){    int ret=0;    while(x)    {        int l=dfn[top[x]],r=dfn[x];        ret+=query(1,1,n,l,r,0);        update(1,1,n,l,r,1);        x=fa[top[x]];    }    return ret;}int main(){    n=rd();    for(int i=2;i<=n;i++)    {        fa[i]=rd()+1;        edge[++ct]=N(i,head[fa[i]]);head[fa[i]]=ct;    }    dfs(1); top[1]=1; dfs2(1); build(1,1,n);    m=rd(); char ch[15];    for(int i=1,x;i<=m;i++)    {        scanf("%s",&ch); x=rd()+1;        if(ch[0]=='u')        {            printf("%d\n",query(1,1,n,dfn[x],end[x],1));            update(1,1,n,dfn[x],end[x],0);        }        if(ch[0]=='i')        {            printf("%d\n",ask(x));        }    }    return 0;}