记录编号	243435	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.224 s
提交时间	2016-03-29 22:11:06	内存使用	16.69 MiB

#include<cstdio>	//need change at install
#include<algorithm>
using namespace std;

const int maxl=100010;
int n,q,x,fa[maxl],next[maxl],head[maxl],tail[maxl],f[maxl];
int i,j,son[maxl],sum[maxl],he[maxl],hash[maxl],c,flect[maxl],co,top[maxl];
char s[60];

void dfs(int x){
	sum[x]=1;
	for (int i=head[x];i!=0;i=next[i]){
		dfs(son[i]);
		sum[x]+=sum[son[i]];
	}
	return;
}

void mark(int x){
	hash[x]=++c;
	if (c!=hash[fa[x]]+1){
		flect[hash[x]]=++co;top[co]=hash[x];
	}
	else flect[hash[x]]=co;
	for (int i=head[x];i!=0;i=next[i]) mark(son[i]);
	return;
}

struct leave{
	int l,r,v,mark;//mark=1 means need install else need uninstall;
}t[maxl<<3];

void mtree(int x){
	if (t[x].l==t[x].r) return;
	int m=(t[x].l+t[x].r)>>1;
	t[x*2].l=t[x].l;
	t[x*2].r=m;
	t[x*2+1].l=m+1;
	t[x*2+1].r=t[x].r;
	mtree(x*2);mtree(x*2+1);
	return;
}

int find(int x,int l,int r){
	int i,d;
	if (t[x].mark==1) t[x].v=t[x].r-t[x].l+1;
	if (t[x].mark==2) t[x].v=0;
	if (t[x].mark!=0){
		t[x*2].mark=t[x*2+1].mark=t[x].mark;
		t[x].mark=0;
	}
	if (t[x].r<l||t[x].l>r) return 0;
	//printf("%d %d %d\n",t[x].l,t[x].r,t[x].v);
	if (t[x].l>=l&&t[x].r<=r) return t[x].v;
	return find(x*2,l,r)+find(x*2+1,l,r);
}

void change(int x,int l,int r,int y){
	if (t[x].r<l||t[x].l>r) return;
	if (t[x].mark==1) t[x].v=t[x].r-t[x].l+1;
	if (t[x].mark==2) t[x].v=0;
	if (t[x].mark!=0){
		t[x*2].mark=t[x*2+1].mark=t[x].mark;
		t[x].mark=0;
	}
	if (t[x].l>=l&&t[x].r<=r){
		int i,d;
		if (y==1) d=t[x].r-t[x].l+1-t[x].v;
			else d=-t[x].v;
		for (i=x;i>0;i/=2) t[i].v+=d;
		t[x*2].mark=t[x*2+1].mark=y;
		t[x].mark=0;
		return;
	}
	change(x*2,l,r,y);
	change(x*2+1,l,r,y);
	return;
}

int install(int x){
	int ans=0,i=x;
	//printf("install %d\n",x);
	while (i!=0){
		//printf("%d %d\n",top[flect[i]],i);
		ans+=i-top[flect[i]]+1-find(1,top[flect[i]],i);
		change(1,top[flect[i]],i,1);
		i=f[top[flect[i]]];
	}
	return ans;
}

int uninstall(int x){
	//printf("uninstall %d\n",x);
	//printf("%d %d\n",x,x+he[x]-1);
	int ans=find(1,x,x+he[x]-1);
	change(1,x,x+he[x]-1,2);
	return ans;
}

void bianli(int x){
	printf("%d %d %d %d\n",t[x].l,t[x].r,t[x].v,t[x].mark);
	if (t[x].l==t[x].r) return;
	bianli(x<<1);bianli((x<<1)|1);
	return;
}

int main()
{
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<n;i++){
		scanf("%d",&fa[i]);
		son[i]=i;
		if (head[fa[i]]==0) head[fa[i]]=tail[fa[i]]=i;
			else{
				next[tail[fa[i]]]=i;tail[fa[i]]=i;
			}
	}
	
	dfs(0);
	for (i=0;i<n;i++){
		for (j=head[i];j!=0;j=next[j])
		if (sum[son[j]]>sum[son[head[i]]]) 
			swap(son[j],son[head[i]]);
	}
	
	mark(0);
	for (i=0;i<n;i++){
		f[hash[i]]=hash[fa[i]];
		he[hash[i]]=sum[i];
	}
	f[1]=0;
	
	t[1].l=1;t[1].r=n;
	mtree(1);
	
	scanf("%d",&q);
	for (i=1;i<=q;i++){
		scanf("%s%d",&s,&x);
		x=hash[x];
		//printf("%s %d\n",s,x);
		printf("%d\n",(s[0]=='i')?install(x):uninstall(x));
		/*printf("\n");
		bianli(1);*/
	}
	return 0;
}