http://uoj.ac/problem/128
https://www.luogu.org/problemnew/show/P2146

思路：0表示未安装，1表示已安装，就是裸的树剖操作了。注意题目数据是0开始，加个1，从1开始。

#include<bits/stdc++.h>
using namespace std;
#define maxn (100000+100)

int n,m,dfs_clock;
int sz[maxn],fa[maxn],deep[maxn],son[maxn],top[maxn],w[maxn],id[maxn],id2[maxn];
vector<int> G[maxn]; 
int ql,qr,val,setv[maxn*4],sumv[maxn*4],_sum;

void dfs1(int u)
{
    deep[u]=deep[fa[u]]+1;
    sz[u]=1;
    int maxx=0;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[v]>maxx){son[u]=v;maxx=sz[v];}
    }
}

void dfs2(int u,int up)
{
    id[u]=id2[u]=++dfs_clock;
    top[u]=up;
    if(son[u]){dfs2(son[u],up);id2[u]=id2[son[u]];}
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==son[u])continue;
        dfs2(v,v);
        id2[u]=id2[v];
    }
}

void build(int o,int l,int r)
{
    if(l==r)setv[o]=0;
    else setv[o]=-1;
}

void pushdown(int o)
{
    if(setv[o]>=0)
    {
        setv[o*2]=setv[o*2+1]=setv[o];
        setv[o]=-1;
    }
}

void maintain(int o,int l,int r)
{
    if(setv[o]>=0)sumv[o]=setv[o]*(r-l+1);
    else sumv[o]=sumv[o*2]+sumv[o*2+1];
}

void update(int o,int l,int r)
{
    if(ql<=l&&qr>=r)setv[o]=val;
    else
    {
        int mid=(l+r)/2;
        pushdown(o);
        if(ql<=mid)update(o*2,l,mid); else maintain(o*2,l,mid);
        if(qr>mid)update(o*2+1,mid+1,r); else maintain(o*2+1,mid+1,r);
    }
    maintain(o,l,r); 
}

void query(int o,int l,int r)
{
    if(setv[o]>=0)_sum+=setv[o]*(min(r,qr)-max(l,ql)+1);
    else if(ql<=l&&qr>=r)_sum+=sumv[o];
    else
    {
        int mid=(l+r)/2;
        if(ql<=mid)query(o*2,l,mid);
        if(qr>mid)query(o*2+1,mid+1,r);
    }
}

int Query1(int u,int v)
{
    int num=deep[u];
    _sum=0;
    int tp1=top[u],tp2=top[v];
    while(tp1!=tp2)
    {
        if(deep[tp1]<deep[tp2]){swap(tp1,tp2);swap(u,v);}
        ql=id[tp1],qr=id[u];
        query(1,1,n);
        u=fa[tp1];
        tp1=top[u];
    }
    if(deep[u]>deep[v])swap(u,v);
    ql=id[u],qr=id[v];
    query(1,1,n);
    return num-_sum;
}

void Update1(int u,int v)
{
    int tp1=top[u],tp2=top[v];
    while(tp1!=tp2)
    {
        if(deep[tp1]<deep[tp2]){swap(tp1,tp2);swap(u,v);}
        ql=id[tp1],qr=id[u],val=1;
        update(1,1,n);
        u=fa[tp1];
        tp1=top[u];
    }
    if(deep[u]>deep[v])swap(u,v);
    ql=id[u],qr=id[v],val=1;
    update(1,1,n);
}

int Query2(int u)
{
    _sum=0;
    ql=id[u],qr=id2[u];
    query(1,1,n);
    return _sum;
}

void Update2(int u)
{
    ql=id[u],qr=id2[u],val=0;
    update(1,1,n);
}

int main()
{
    //freopen("input.in","r",stdin);
    char op[10]; 
    int x;
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&x);
        fa[i]=x+1;
        G[x+1].push_back(i);
    }
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s%d",op,&x);
        x++;
        if(op[0]=='i')
        {
            printf("%d\n",Query1(x,1));
            Update1(x,1);
        }
        else
        {
            printf("%d\n",Query2(x));
            Update2(x);
        }     
    }
    return 0;
}