记录编号	312259	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	cdcq	是否通过	通过
代码语言	C++	运行时间	7.963 s
提交时间	2016-09-25 21:23:38	内存使用	92.36 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){int z=0,mark=1;  char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')mark=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
	return z*mark;
}
struct ddd{int next,y;}e[110000];int LINK[110000],ltop=0;
inline void insert(int x,int y){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;}
int n,m;
int size[110000],deep[110000],father[110000],big_child[110000],top[110000],n_value[110000];
int dfs_xv[110000],fan_xv[110000],er_xv[110000],xv_cnt=-1;//注意因为从0开始，所以总共有7个点，但是编号只到6
void dfs1(int x,int _father,int _deep){
	father[x]=_father,deep[x]=_deep,size[x]=1;
	int max_size=0,max_child=-1;//注意0有意义
	for(int i=LINK[x];i;i=e[i].next)if(e[i].y!=father[x]){
		dfs1(e[i].y,x,_deep+1);
		size[x]+=size[e[i].y];
		if(size[e[i].y]>max_size)  max_size=size[e[i].y],max_child=e[i].y;
	}
	big_child[x]=max_child;
}
void dfs2(int x,int _top){
	top[x]=_top;  dfs_xv[++xv_cnt]=x;  fan_xv[x]=xv_cnt;
	if(big_child[x]!=-1)  dfs2(big_child[x],_top);//注意-1
	for(int i=LINK[x];i;i=e[i].next)if(e[i].y!=father[x] && e[i].y!=big_child[x])
		dfs2(e[i].y,e[i].y);
	er_xv[x]=xv_cnt;
}
struct dcd{int sleft,sright,mid,svalue,delta;}tree[5100000];
void stev(int x){  tree[x].svalue=tree[x].delta*(tree[x].sright-tree[x].sleft+1);}//sxysxy_orz
void get_SegmentTree(int x,int _left,int _right){
	tree[x].sleft=_left,tree[x].sright=_right,tree[x].mid=(_left+_right)>>1;
	tree[x].svalue=tree[x].delta=0;
	if(_left!=_right)  get_SegmentTree(x<<1,_left,tree[x].mid),get_SegmentTree(x<<1|1,tree[x].mid+1,_right);
}
int search(int x,int _left,int _right){
	if(tree[x].sleft==_left && tree[x].sright==_right)  return tree[x].svalue;
	else{
		if(tree[x].delta!=-1){
			tree[x<<1].delta=tree[x<<1|1].delta=tree[x].delta;  tree[x].delta=-1;//注意这里并不是加上，而是设置为，注意-1 (sxysxy_orz
			stev(x<<1),stev(x<<1|1);
			tree[x].delta=-1;
		}
		if(_left<=tree[x].mid && _right>tree[x].mid)  return search(x<<1,_left,tree[x].mid)+search(x<<1|1,tree[x].mid+1,_right);
		else if(_right<=tree[x].mid)  return search(x<<1,_left,_right);
		else  return search(x<<1|1,_left,_right);
	}
}
void buff(int x,int _left,int _right,int z){
	if(tree[x].sleft==_left && tree[x].sright==_right)  tree[x].delta=z,stev(x);
	else{
		if(tree[x].delta!=-1){
			tree[x<<1].delta=tree[x<<1|1].delta=tree[x].delta;  tree[x].delta=-1;
			stev(x<<1),stev(x<<1|1);
			tree[x].delta=-1;
		}
		if(_left<=tree[x].mid && _right>tree[x].mid)  buff(x<<1,_left,tree[x].mid,z),buff(x<<1|1,tree[x].mid+1,_right,z);
		else if(_right<=tree[x].mid)  buff(x<<1,_left,_right,z);
		else  buff(x<<1|1,_left,_right,z);
		tree[x].svalue=tree[x<<1].svalue+tree[x<<1|1].svalue;
	}
}
int install(int x){
	int ans=0;
	while(x!=-1){
		ans+=fan_xv[x]-fan_xv[top[x]]+1-search(1,fan_xv[top[x]],fan_xv[x]);
		buff(1,fan_xv[top[x]],fan_xv[x],1);
		//x=father[x]  我是傻逼qaqqqqqqqqqqqqqqqqqqqq
		x=father[top[x]];
	}
	return ans;
}
int uninstall(int x){
	int ans=search(1,fan_xv[x],er_xv[x]);
	buff(1,fan_xv[x],er_xv[x],0);
	return ans;
}
int main(){
	/*freopen("ddd.in","r",stdin);
	freopen("ddd.out","w",stdout);*/
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	cin>>n;
	for(int i=1;i<n;i++)  insert(read(),i),n_value[i]=0;
	dfs1(0,-1,1),dfs2(0,0),get_SegmentTree(1,0,n-1);
	cin>>m;
	char ch;  int _id;
	while(m --> 0){//趋向于
		ch=getchar(); 
	   	while(ch!='i' && ch!='u')  ch=getchar();
		if(ch=='i'){
			for(int i=1;i<=6;i++)  ch=getchar();
			_id=read();
			printf("%d\n",install(_id));
		}
		else{
			for(int i=1;i<=8;i++)  ch=getchar();
			_id=read();
			printf("%d\n",uninstall(_id));
		}
	}
	return 0;
}