题目大意：有n个软件安装包，除第一个以外，其他的要在另一个安装包的基础上安装，且无环，问在安装和卸载某个软件包时，这个操作实际上会改变多少个软件包的安装状态。

思路：可构成树，用树链剖分，线段树。已安装的为1，未安装的为0。

对于安装操作，就是询问x到0的路径上0的个数，然后把这个路径赋为1

对于卸载操作，就是询问x的子树中1的个数，然后把子树赋为0。

代码：

#include<cstdio>
#include<iostream>
#define M 800500
using namespace std;

int n,cnt,dfn,hson[M],pa[M],id[M],to[M],top[M],vis[M],last[M],next[M],head[M],deep[M],size[M],sum[M],sz[M],lazy[M];

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs1(int x)
{
    size[x]=1;
    for (int i=head[x];i;i=next[i])
        if (to[i]!=pa[x])
        {
            pa[to[i]]=x,deep[to[i]]=deep[x]+1;
            dfs1(to[i]),size[x]+=size[to[i]];
            if (size[to[i]]>size[hson[x]]) hson[x]=to[i];
        }
}

void dfs2(int x,int tp)
{
    id[x]=++dfn,top[x]=tp;
    if (hson[x]) dfs2(hson[x],tp);
    for (int i=head[x];i;i=next[i])
        if (to[i]!=pa[x]&&to[i]!=hson[x]) dfs2(to[i],to[i]);
    last[x]=dfn;
}

void build(int l,int r,int cur)
{
     if (l==r) { sum[cur]=0,lazy[cur]=-1,sz[cur]=1; return; }
     int mid=l+r>>1;
     build(l,mid,cur<<1),build(mid+1,r,cur<<1|1);
     sz[cur]=sz[cur<<1]+sz[cur<<1|1];
}

void push_down(int k)
{
     if (lazy[k]!=-1)
     {
          sum[k<<1]=sz[k<<1]*lazy[k],sum[k<<1|1]=sz[k<<1|1]*lazy[k];
          lazy[k<<1]=lazy[k<<1|1]=lazy[k],lazy[k]=-1;
     }
}

void change(int L,int R,int l,int r,int cur,int val)
{
     if (L==l && R==r) { sum[cur]=val*sz[cur]; lazy[cur]=val; return; }
     int mid=L+R>>1; push_down(cur);
     if (r<=mid) change(L,mid,l,r,cur<<1,val);
     else if (l>mid) change(mid+1,R,l,r,cur<<1|1,val);
          else change(L,mid,l,mid,cur<<1,val),change(mid+1,R,mid+1,r,cur<<1|1,val);
     sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}

int ask(int L,int R,int l,int r,int cur)
{
    if (L==l && R==r) return sum[cur];
    int mid=L+R>>1; push_down(cur);
    if (r<=mid) return ask(L,mid,l,r,cur<<1);
    else if (l>mid) return ask(mid+1,R,l,r,cur<<1|1);
         else return ask(L,mid,l,mid,cur<<1)+ask(mid+1,R,mid+1,r,cur<<1|1);
}

void add(int x,int y)
{
     if (deep[x]<deep[y]) swap(x,y);
     int sum=0,t=deep[x]-deep[y]+1;
     for (;top[x]!=top[y];x=pa[top[x]])
     {         
         if (deep[top[x]]<deep[top[y]]) swap(x,y);
         sum+=ask(1,n,id[top[x]],id[x],1);
         change(1,n,id[top[x]],id[x],1,1);
     }
     if (deep[x]>deep[y]) swap(x,y);
     sum+=ask(1,n,id[x],id[y],1);
     change(1,n,id[x],id[y],1,1);
     printf("%d\n",t-sum);
}

int main()
{
    int i,m,x;
    scanf("%d",&n);
    for (i=1;i<n;i++) scanf("%d",&m),ins(m+1,i+1);
    scanf("%d",&m),dfs1(1),dfs2(1,1),build(1,n,1);
    for (i=1;i<=m;i++)
    {
        char ch[20];
        scanf("%s%d",ch,&x),x++;
        if (ch[0]=='i') add(1,x);
        else printf("%d\n",ask(1,n,id[x],last[x],1)),change(1,n,id[x],last[x],1,0);
    }
    return 0;
}