记录编号	437909	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	3.132 s
提交时间	2017-08-14 21:07:13	内存使用	2.98 MiB

#include<cstdio>
#include<cctype>
#include<cstring>
#define mid_a ((l+r)>>1)
#define mid_b ((now->l+now->r)>>1)
const int maxn=1e5+5;
using namespace std;
struct edge
{
	int fr,to;
	edge *nt;
	edge(){fr=to=0;nt=NULL;}
}*e[maxn];
struct stree
{
	int l,r,all,lazy;
	stree *ls,*rs,*fa;
	stree(){l=r=all=lazy=0;ls=rs=fa=NULL;}
}*root;
inline int get();
edge *add(int fr,int to);
void dfs_a(edge *now);
void dfs_b(edge *now);
stree *build(int l,int r);
void search_u(stree *now,int l,int r);
void update(stree *now,bool j);
void up(stree *now);
void search_i(stree *now,int l,int r);
int n,q,temp;
int siz[maxn],fa[maxn],son[maxn],top[maxn],dfn[maxn],atdfn[maxn],dfsn;
int res,numb;
int main()
{
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	n=get();
	for(int i=1;i<n;i++)
	{
		temp=get();
		e[i]=add(i,temp);
		e[temp]=add(temp,i);
	}
	memset(son,-1,sizeof(son));
	dfs_a(e[0]);
	dfs_b(e[0]);
	q=get();
	root=build(1,n);
	for(int i=1;i<=q;i++)
	{
		register char t=getchar();
		if(t=='i')
		{
			numb=get();
			int cur=top[numb];
			if(numb)
			{
				while(numb!=0)
				{
					search_i(root,dfn[cur],dfn[numb]);
					if(!fa[cur])search_i(root,dfn[0],dfn[0]);
					numb=fa[cur];cur=top[fa[cur]];
				}
			}
			else search_i(root,dfn[0],dfn[0]);
			printf("%d\n",res);
			res=0;
		}
		else 
		{
			numb=get();
			search_u(root,dfn[numb],dfn[numb]+siz[numb]-1);
			printf("%d\n",res);
			res=0;
		}
	}
	return 0;
}
void search_i(stree *now,int l,int r)
{
	if(now->lazy==1)update(now,false);
	else if(now->lazy==2)update(now,true);
	if(now->l==l&&now->r==r)
	{
		res+=now->all;
		update(now,true);
		now->all=0;now->lazy=0;
		up(now->fa);
	}
	else if(r<=mid_b)search_i(now->ls,l,r);
	else if(l>mid_b)search_i(now->rs,l,r);
	else 
	{
		search_i(now->ls,l,mid_b);
		search_i(now->rs,mid_b+1,r);
	}
}
void up(stree *now)
{
	while(now!=NULL)
	{
		now->all=now->ls->all+now->rs->all;
		now=now->fa;
	}
}
void update(stree *now,bool j)
{
	if(!j&&now->ls!=NULL)
	{
		now->ls->lazy=1;now->ls->all=(now->ls->r-now->ls->l+1);
		now->rs->lazy=1;now->rs->all=(now->rs->r-now->rs->l+1);
		now->lazy=0;
	}
	else if(j&&now->ls!=NULL)
	{
		now->ls->lazy=2;now->ls->all=0;
		now->rs->lazy=2;now->rs->all=0;
		now->lazy=0;
	}
}
void search_u(stree *now,int l,int r)
{
	if(now->lazy==1)update(now,false);
	else if(now->lazy==2)update(now,true);
	if(now->l==l&&now->r==r)
	{
		res+=(now->r-now->l+1-now->all);
		update(now,false);
		now->all=now->r-now->l+1;now->lazy=0;
		up(now->fa);
	}
	else if(r<=mid_b)search_u(now->ls,l,r);
	else if(l>mid_b)search_u(now->rs,l,r);
	else 
	{
		search_u(now->ls,l,mid_b);
		search_u(now->rs,mid_b+1,r);
	}
}
stree *build(int l,int r)
{
	stree *p=new stree();
	p->l=l;p->r=r;
	if(l==r)p->all=1;
	else 
	{
		p->ls=build(l,mid_a);
		p->rs=build(mid_a+1,r);
		p->ls->fa=p;
		p->rs->fa=p;
		p->all=p->ls->all+p->rs->all;
	}
	return p;
}
void dfs_b(edge *now)
{
	register int fr=now->fr;
	dfn[fr]=++dfsn;
	atdfn[dfsn]=fr;
	if(son[fr]!=-1)top[son[fr]]=top[fr],dfs_b(e[son[fr]]);
	while(now!=NULL)
	{
		if(now->to!=fa[fr]&&now->to!=son[fr])top[now->to]=now->to,dfs_b(e[now->to]);
		now=now->nt;
	}
}
void dfs_a(edge *now)
{
	register int fr=now->fr;
	siz[fr]++;
	while(now!=NULL)
	{
		if(fa[fr]==now->to){now=now->nt;continue;}
		fa[now->to]=fr;
		dfs_a(e[now->to]);
		if(siz[now->to]>siz[son[fr]]||son[fr]==-1)son[fr]=now->to;
		siz[fr]+=siz[now->to];
		now=now->nt;
	}
}
edge *add(int fr,int to)
{
	edge *p=new edge();
	p->fr=fr;p->to=to;
	p->nt=e[fr];
	return p;
}
inline int get()
{
	int t=0,j=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}