记录编号	220434	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	9.668 s
提交时间	2016-01-18 16:21:36	内存使用	25.44 MiB

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define maxn 100050
using namespace std;
int n,q;
class settree{
private:
	struct node{
		int l,r;
		int ins,la;
		int lazy;
	}ns[maxn*8];
public:
	void build(int i,int l,int r){
		ns[i].l=l;ns[i].r=r;
		if(l==r)return;
		build(i*2,l,(l+r)/2);
		build(i*2+1,(l+r)/2+1,r);
	}
	int query(int i,int l,int r,bool statu){
		int ans=0;
		if(ns[i].lazy){
			if(ns[i].lazy==1){
				ns[i*2].ins=0;
				ns[i*2+1].ins=0;
			}else{
				ns[i*2].ins=ns[i*2].r-ns[i*2].l+1;
				ns[i*2+1].ins=ns[i*2+1].r-ns[i*2+1].l+1; 
			}
		 	ns[i*2].lazy=ns[i].lazy;
			ns[i*2+1].lazy=ns[i].lazy;
			ns[i].lazy=0;
		}
		if(l==ns[i].l&&r==ns[i].r){
			ns[i].lazy=(int)statu+1;
			int tmp=ns[i].ins;
			if(statu){
				ns[i].ins=r-l+1;
				return ns[i].ins-tmp;
			}else{
				ns[i].ins=0;
				return tmp;
			}
		}
		else if(r<=ns[i*2].r)ans=query(i*2,l,r,statu);
		else if(l>=ns[i*2+1].l)ans=query(i*2+1,l,r,statu);
		else if(l<=ns[i*2].r&&r>=ns[i*2+1].l)ans=query(i*2,l,ns[i*2].r,statu)+query(i*2+1,ns[i*2+1].l,r,statu);
		ns[i].ins=ns[i*2].ins+ns[i*2+1].ins;
		return ans;
	}
}st;
class cuttree{
private:
	struct edge{
		int ne,fr,to;
	}e[maxn*8];
	int head[maxn],es;
	int intree[maxn],outree[maxn],tot;
	bool data[maxn];
	int top[maxn];
	int fa[maxn];
	int deep[maxn];
	int size[maxn];
	int son[maxn];
	int maxdeep[maxn];
public:
	void addedge(int fr,int to){
		es++;e[es].fr=fr;e[es].to=to;e[es].ne=head[fr];head[fr]=es;
	}
	void build(){
		dfs1(0,0,1);
		dfs2(0,0);
		fa[0]=-1;
	}
	void dfs1(int now,int f,int de){
		fa[now]=f;deep[now]=de;size[now]=1;
		int to;
		for(int i=head[now];i;i=e[i].ne){
			to=e[i].to;
			if(to==f)continue;
			dfs1(to,now,de+1);
			size[now]+=size[to];
			if((!son[now])||size[son[now]]<size[to])son[now]=to;
		}
	}
	void dfs2(int now,int t){
		int tmp;
		top[now]=t;intree[now]=++tot;outree[tot]=now;
		if(!son[now]){
			maxdeep[now]=tot;
			return;
		}
		dfs2(son[now],t);
		maxdeep[now]=max(maxdeep[now],maxdeep[son[now]]);
		int to;
		for(int i=head[now];i;i=e[i].ne){
			to=e[i].to;
			if(to==son[now]||to==fa[now])continue;
			dfs2(to,to);
			maxdeep[now]=max(maxdeep[now],maxdeep[to]);
		}
	}
	int gettot(){
		return tot;
	}
	int install(int now){
		int ans=0;
		while(now!=-1){
			ans+=st.query(1,intree[top[now]],intree[now],1);
			if(now==top[now]){
				now=fa[now];continue;
			}
			now=top[now];
		}
		return ans;
	}
	int uninstall(int now){
		int ans=0;
		int to;
		int l=intree[now],r=maxdeep[now];
		ans=st.query(1,l,r,0);
		return ans;
	}
}ct;
void solve(){
	ct.build();
	st.build(1,1,ct.gettot());
	scanf("%d",&q);
	char tmp[20];
	int tar;
	for(int i=1;i<=q;i++){
		scanf("%s",tmp);
		scanf("%d",&tar);
		if(tmp[0]=='i')printf("%d\n",ct.install(tar));
		else printf("%d\n",ct.uninstall(tar));
	}
}
void read(){
	scanf("%d",&n);
	int tmp;
	for(int i=1;i<=n-1;i++){
		scanf("%d",&tmp);
		ct.addedge(tmp,i);
	}
}
int main(){
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	read();
	solve();
	return 0;
}