#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,p[N],dep[N],fa[N],sz[N],son[N],tp[N],dn[N],cnt[N];
vector<int> s[N],w[N];
struct qh{
    int v,nt;
}E[N<<1];
inline int Rd(){
    int s=0,w=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}
void add(int u,int v){E[++p[0]]=(qh){v,p[u]};p[u]=p[0];return ;}
void d1(int x,int f){
    dep[x]=dep[f]+1;fa[x]=f;sz[x]=1;int mx=0;
    for(int i=p[x];i;i=E[i].nt){
        int v=E[i].v;
        if(v==f) continue;
        d1(v,x);
        sz[x]+=sz[v];
        if(sz[v]>mx) son[x]=v,mx=sz[v];
    }return ;
}
void d2(int x,int t){
    tp[x]=t;
    if(son[x]) d2(son[x],t);
    else dn[t]=x;
    for(int i=p[x];i;i=E[i].nt){
        int v=E[i].v;
        if(v==fa[x]||v==son[x]) continue;
        s[tp[x]].push_back(v);
        w[tp[x]].push_back(x);
        d2(v,v);
    }return ;
}
int in1(int x){
    if(!x||cnt[tp[x]]>=dep[x]-dep[tp[x]]+1) return 0;
    if(cnt[tp[x]]){
        int nw=dep[x]-dep[tp[x]]+1-cnt[tp[x]];
        cnt[tp[x]]=dep[x]-dep[tp[x]]+1;
        return nw;
    }
    else{
        cnt[tp[x]]=dep[x]-dep[tp[x]]+1;
        return dep[x]-dep[tp[x]]+1+in1(fa[tp[x]]);
    }
}
int tc(int t,int x){
    int l=0,r=w[t].size()-1,ans=-1;
    while (l<=r){
        int m=l+r>>1;
        if(w[t][m]>=x) l=m+1,ans=m;
        else r=m-1;
    }
    return ans;
}
int in2(int x){
    if(cnt[tp[x]]<=dep[x]-dep[tp[x]]) return 0;
    int nw=cnt[tp[x]]-(dep[x]-dep[tp[x]]);
    cnt[tp[x]]=dep[x]-dep[tp[x]];
    int in=tc(tp[x],x);
    if(in==-1) return nw;
    // printf("%d\n",nw);
    for(int i=in;i>=0;i--) nw+=in2(s[tp[x]][i]);
    return nw;
}
int main(){
    // freopen("software.in","r",stdin);
    // freopen("software.out","w",stdout);
    n=Rd();
    for(int i=2;i<=n;i++){
        int x=Rd()+1;
        add(x,i);add(i,x);
    }
    d1(1,0);
    d2(1,1);
    q=Rd();
    for(int i=1;i<=q;i++){
        char Q[10];cin>>Q;
        if(Q[0]=='i'){
            int x=Rd()+1;
            printf("%d\n",in1(x));
        }
        else{
            int x=Rd()+1;
            printf("%d\n",in2(x));
        }
    }
    return 0;
}

TLE了几个点，但时间复杂度目测nlogn

树链剖分的重链轻边均不超过logn，那为什么TLE呢？