记录编号	477050	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	3.654 s
提交时间	2017-11-28 20:47:17	内存使用	7.54 MiB

#define maxn 100010
#define lson l,mid,t
#define rson mid+1,r,t|1

#include<cstdio>

char s[20];
int posl,posr,pos;
int mark[maxn<<2],rdfn[maxn],val;
int n,q,index,fa[maxn],top[maxn],son[maxn];
int tree[maxn<<2],idx[maxn],tot,first[maxn],siz[maxn];

struct tree_edge{int v,next;}edge[maxn<<1];

void add(int u,int v)
{
	edge[++tot].v=v;
	edge[tot].next=first[u];
	first[u]=tot;
}

void dfs1(int rt)
{
	siz[rt]=1;
	for(int i=first[rt];i;i=edge[i].next)
		if(edge[i].v!=fa[rt]){
			dfs1(edge[i].v);
			siz[rt]+=siz[edge[i].v];
			if(siz[edge[i].v]>siz[son[rt]])
				son[rt]=edge[i].v;
		}
}

void dfs2(int rt)
{
	idx[rt]=++index;
	if(!son[rt]){rdfn[rt]=index;return;}
	top[son[rt]]=top[rt];dfs2(son[rt]);
	for(int i=first[rt];i;i=edge[i].next)
		if(edge[i].v!=fa[rt]&&edge[i].v!=son[rt])
			top[edge[i].v]=edge[i].v,dfs2(edge[i].v);
	rdfn[rt]=index;
}

void clear(int l,int r,int rt)
{
	if(mark[rt]!=0){
		int mid=(l+r)>>1,t=rt<<1;
		if(mark[rt]==1){
			tree[t]=mid-l+1;
			tree[t|1]=r-mid;
			mark[t]=mark[t|1]=1;
			mark[rt]=0;return;
		}
		tree[t]=tree[t|1]=0;
		mark[t]=mark[t|1]=-1;
		mark[rt]=0;return;
	}
}

int query(int l,int r,int rt)
{
	if(posl<=l&&posr>=r)return tree[rt];
	int mid=(l+r)>>1,t=rt<<1,res=0;clear(l,r,rt);
	if(posl<=mid)res+=query(lson);
	if(posr> mid)res+=query(rson);
	return res;
}

void modify(int l,int r,int rt)
{
	if(posl<=l&&posr>=r){
		if(val==1){tree[rt]=r-l+1;mark[rt]=1;}
		else {tree[rt]=0;mark[rt]=-1;}
		return;
	}
	int mid=(l+r)>>1,t=rt<<1;clear(l,r,rt);
	if(posl<=mid)modify(lson);
	if(posr>mid) modify(rson);
	tree[rt]=tree[t]+tree[t|1];
}

void install(int x)
{
	int res=0,cnt=0;val=1;
	while(top[x]!=1){
		posl=idx[top[x]];posr=idx[x];
		cnt+=posr-posl+1;
		res+=query(1,n,1);modify(1,n,1);
		x=fa[top[x]];
	}	
	posl=idx[1];posr=idx[x];
	cnt+=posr-posl+1;
	res+=query(1,n,1);modify(1,n,1);
	printf("%d\n",cnt-res);
}

void uninstall(int x)
{
	posl=idx[x];posr=rdfn[x];val=-1;
	int res=query(1,n,1);modify(1,n,1);
	printf("%d\n",res);
}

int main()
{
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		scanf("%d",&fa[i]),fa[i]++;
		add(fa[i],i);add(i,fa[i]);
	}
	dfs1(1);top[1]=1;dfs2(1);
	scanf("%d",&q);
	for(int i=1,x;i<=q;i++){
		scanf("%s%d",s+1,&x);
		if(s[1]=='i')install(x+1);
		else uninstall(x+1);
	}
}