【题目大意】
如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环。求出在安装和卸载某个软件包时，实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包。（注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0）
【思路】
裸的树剖...然而我发现我写错了区间覆盖的线段树，要设置两个标记，一个记录该区间是否需要修改，另一个记录该区间覆盖的值。
话说BZOJ要用printf否则会RE，我怎么不长记性呢………
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN=+;
const int rt=;
vector<int> E[MAXN];
int n;
int fa[MAXN],dep[MAXN],hson[MAXN],size[MAXN];
int cnt=,top[MAXN],pos[MAXN];
int sum[MAXN<<],add[MAXN<<],change[MAXN<<]; //树链剖分部分
void addedge(int u,int v)
{
E[u].push_back(v);
} void dfs1(int u,int father,int depth)
{
fa[u]=father;
dep[u]=depth;
size[u]=;
hson[u]=-;
for (int i=;i<E[u].size();i++)
{
int to=E[u][i];
dfs1(to,u,depth+);
size[u]+=size[to];
if (hson[u]==- || size[to]>size[hson[u]]) hson[u]=to;
}
} void dfs2(int u,int t)
{
pos[u]=++cnt;
top[u]=t;
if (hson[u]!=-) dfs2(hson[u],t);
for (int i=;i<E[u].size();i++)
{
int to=E[u][i];
if (to!=hson[u]) dfs2(to,to);
}
} //线段树部分
void build()
{
memset(sum,,sizeof(sum));
memset(add,,sizeof(add));
} void pushup(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
} void pushdown(int rt,int m)
{
if (change[rt])
{
change[rt<<]=change[rt<<|]=;
add[rt<<]=add[rt];
add[rt<<|]=add[rt];
sum[rt<<]=add[rt]*(m-(m>>));
sum[rt<<|]=add[rt]*(m>>);
add[rt]=change[rt]=;
}
} int query_sum(int L,int R,int l,int r,int rt)
{
if (L<=l && r<=R) return sum[rt];
pushdown(rt,r-l+);
int m=(l+r)>>;
int ret=;
if (m>=L) ret+=query_sum(L,R,lson);
if (m<R) ret+=query_sum(L,R,rson);
pushup(rt);
return ret;
} void modify(int L,int R,int l,int r,int rt,int x)
{
if (L<=l && r<=R)
{
change[rt]=;
add[rt]=x;
sum[rt]=(r-l+)*x;
return;
}
pushdown(rt,r-l+);
int m=(l+r)>>;
if (m>=L) modify(L,R,lson,x);
if (m<R) modify(L,R,rson,x);
pushup(rt);
} //树链剖分查询部分
int install(int x,int y)
{
int ret=dep[x],f1=top[x],f2=top[y];
while (f1!=f2)
{
ret-=query_sum(pos[f1],pos[x],,n,);
modify(pos[f1],pos[x],,n,,);
x=fa[f1];
f1=top[x];
}
ret-=query_sum(pos[y],pos[x],,n,);
modify(pos[y],pos[x],,n,,);
return (ret);
} int uninstall(int x)
{
int ret=query_sum(pos[x],pos[x]+size[x]-,,n,);
modify(pos[x],pos[x]+size[x]-,,n,,);
return ret;
} //读入部分
void init()
{
scanf("%d",&n);
for (int i=;i<n;i++)
{
int tmp;
scanf("%d",&tmp);
addedge(tmp,i);
}
dfs1(,,);
dfs2(,);
} void get_ans()
{
memset(sum,,sizeof(sum));
memset(change,,sizeof(change));
memset(add,,sizeof(add));
int q;
scanf("%d",&q);
for (int i=;i<q;i++)
{
char str[];
int x;
scanf("%s%d",str,&x);
if (str[]=='i') printf("%d\n",install(x,rt));
else if (str[]=='u') printf("%d\n",uninstall(x));
}
} int main()
{
init();
build();
get_ans();
return ;
}