记录编号	213114	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	7.646 s
提交时间	2015-12-10 11:50:30	内存使用	6.77 MiB

#define lson l,mid,t
#define rson mid+1,r,t|1
#define cson l,r,rt
 
#define MAXN 100010UL
#define MAXC 20UL
 
#include <cstdio>
#include <cstring>
 
struct Edge{int v,nx;};
Edge edge[MAXN];
int n,m,ec,posl,posr,update_val,headlist[MAXN],fa[MAXN],son[MAXN],size[MAXN],cnt,id[MAXN],top[MAXN],mark[MAXN<<2],tree[MAXN<<2],out_sta[MAXN];
char op[MAXC];
 
inline void Add_Edge(int u,int v){
	edge[++ec].v=v;
	edge[ec].nx=headlist[u];
	headlist[u]=ec;
	return;
}
 
inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x;
}
 
void dfs(int p){
	size[p]|=1;
	for(int i=headlist[p];i;i=edge[i].nx){
		dfs(edge[i].v);
		size[p]+=size[edge[i].v];
		if(size[son[p]]<size[edge[i].v]) son[p]=edge[i].v;
	}
	return;
}
 
void build_tree(int p,int tp){
	top[p]=tp;
	id[p]=++cnt;
	if(son[p]) build_tree(son[p],tp);
	for(int i=headlist[p];i;i=edge[i].nx)
		if(son[p]!=edge[i].v) build_tree(edge[i].v,edge[i].v);
	out_sta[p]=cnt;
	return;
}
 
inline void Clear(int l,int r,int rt){
	if(l==r||mark[rt]==-1) return;
	int t=rt<<1,mid=(l+r)>>1;
	mark[t]=mark[t|1]=mark[rt];
	tree[t]=mark[rt]*(mid-l+1);
	tree[t|1]=mark[rt]*(r-mid);
	mark[rt]=-1;
	return;
}
 
int Query(int l,int r,int rt){
	if(posl<=l&&posr>=r)
		return tree[rt];
	int t=rt<<1,mid=(l+r)>>1,Ans=0;
	Clear(cson);
	if(posl<=mid) Ans+=Query(lson);
	if(posr>mid) Ans+=Query(rson);
	return Ans;
}
 
void Update(int l,int r,int rt){
	if(posl<=l&&posr>=r){
		mark[rt]=update_val;
		tree[rt]=(r-l+1)*update_val;
		return;
	}
	int t=rt<<1,mid=(l+r)>>1;
	Clear(cson);
	if(posl<=mid) Update(lson);
	if(posr>mid) Update(rson);
	tree[rt]=tree[t]+tree[t|1]; 
	return;
}
 
inline int Q(int l,int r,int mk){
	if(l>r) return 0;
	posl=l,posr=r;
	if(mk) return r-l+1-Query(1,n,1); 
	else return Query(1,n,1);
}
 
inline void U(int l,int r,int ty){
	if(l>r) return;
	posl=l,posr=r,update_val=ty;
	Update(1,n,1);
	return;
}
 
inline void Install(int p){
	int Ans=0;
	while(top[p]!=1){
		Ans+=Q(id[top[p]],id[p],1);
		U(id[top[p]],id[p],1);
		p=fa[top[p]];
	}
	Ans+=Q(1,id[p],1);
	U(1,id[p],1);
	printf("%d",Ans);
	return;
}
 
inline void UnInstall(int p){
	printf("%d",Q(id[p],out_sta[p],0));
	U(id[p],out_sta[p],0);
	return;
}
 
int main(){
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	n=in();
	memset(mark,-1,sizeof(mark));
	for(int i=2;i<=n;i++) fa[i]=in()+1,Add_Edge(fa[i],i);
	dfs(1);build_tree(1,1);
	scanf("%d",&m);
	for(int i=1,tmp;i<=m;i++,puts("")){
		scanf("%s",op),tmp=in()+1;
		if(op[0]=='i') Install(tmp);
		else UnInstall(tmp);
	}
	return 0;
}