记录编号	482209	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	HT008	是否通过	通过
代码语言	C++	运行时间	4.481 s
提交时间	2018-01-06 17:27:12	内存使用	26.75 MiB

#include <cstdio>
#include <iostream>
#define lson (o<<1),l,mid
#define rson (o<<1)+1,mid+1,r
using namespace std;
const int maxm=210000;
int deep[maxm],son[maxm],size[maxm],fa[maxm],top[maxm];
int head[maxm],to[maxm<<1],net[maxm<<1],cnt;
int p[maxm],val[maxm];
int id[maxm],tot;
int n,m,root;
struct node{
	int l,r,siz,add,sum;
};
node t[maxm*4];
inline void add(int x,int y)
{
	to[++cnt]=y;
	net[cnt]=head[x];
	head[x]=cnt;
}
int dfs1(int now,int fax,int dep)
{
	fa[now]=fax,deep[now]=dep,size[now]=1;
	int maxson=-1;
	for(int i=head[now];i;i=net[i])
	if(to[i]!=fax)
	{
		size[now]+=dfs1(to[i],now,dep+1);
		if(maxson<size[to[i]])
		 son[now]=to[i],maxson=size[to[i]];
	}
	return size[now];
}
void dfs2(int now,int topx)
{
	id[now]=++tot;
	val[tot]=p[now];
	top[now]=topx;
	if(!son[now]) return;
	dfs2(son[now],topx);
    for(int i=head[now];i;i=net[i])
     if(!id[to[i]])
      dfs2(to[i],to[i]);
}
inline void update(int o)
{
	t[o].sum=(t[(o<<1)].sum+t[(o<<1)|1].sum);
}
inline void get_ad(int o,int num)
{
	t[o].sum=t[o].siz*num;
	t[o].add=num;
}
inline void pushdown(int o)
{
	if(t[o].add==-1) return;
	get_ad((o<<1),t[o].add);
	get_ad((o<<1)|1,t[o].add);
	t[o].add=-1;
}
void adj(int o,int ql,int qr,int num)
{
	int l=t[o].l,r=t[o].r;
	if(ql<=l&&qr>=r)
	{
		get_ad(o,num);
		return;
	}
	pushdown(o);
	int mid=(l+r)>>1;
	if(ql<=mid) adj((o<<1),ql,qr,num);
	if(qr>mid) adj((o<<1)|1,ql,qr,num);
	update(o);
}
int ask(int o,int ql,int qr)
{
	int l=t[o].l,r=t[o].r;
	if(ql<=l&&qr>=r)
     return t[o].sum;
	pushdown(o);
	int mid=(l+r)>>1;
	int p1=0,p2=0;
	if(ql<=mid) p1=ask((o<<1),ql,qr);
	if(qr>mid) p2=ask((o<<1)|1,ql,qr);
	return (p1+p2);
}
void build(int o,int l,int r)
{
	t[o].l=l,t[o].r=r,t[o].siz=r-l+1;
	if(l==r)
	{
		t[o].add=-1;
		t[o].sum=val[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lson),build(rson);
	update(o);
}
inline int tree_sum(int u,int v)
{
	int ans=0;
	while(top[u]!=top[v])
	{
		if(deep[top[u]]<deep[top[v]]) swap(u,v);
		ans=(ans+ask(1,id[top[u]],id[u]));
		u=fa[top[u]];
	}
	if(deep[u]<deep[v]) swap(u,v);
	ans=(ans+ask(1,id[v],id[u]));
	return ans;
}
inline void tree_x(int u,int v,int num)
{
	while(top[u]!=top[v])
	{
		if(deep[top[u]]<deep[top[v]]) swap(u,v);
		adj(1,id[top[u]],id[u],num);
		u=fa[top[u]];
	}
	if(deep[u]<deep[v]) swap(u,v);
	adj(1,id[v],id[u],num);
}
inline int read()
{
	int x=0,w=1;char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*w;
}
int main()
{	 
    freopen("manager.in","r",stdin);
    freopen("manager.out","w",stdout);
    n=read(),root=1;
    for(int i=2;i<=n;i++)
     {
     	int u,v;
     	u=read()+1;
     	add(u,i),add(i,u);
     }
    dfs1(root,0,1);
    dfs2(root,root);
    build(1,1,tot);
    char s[9];
	m=read(); 
    for(int i=1;i<=m;i++)
    {
    	int opt,u,v,x;
    	scanf("%s",s);
    	u=read();
    	u++;
    	if(s[0]=='i')
    	{
    		int x=tree_sum(root,u);
    		tree_x(root,u,1);
    		printf("%d\n",tree_sum(root,u)-x);
    	}
    	else
    	{
    		int x=ask(1,id[u],id[u]+size[u]-1);
    		adj(1,id[u],id[u]+size[u]-1,0);
    		printf("%d\n",x-ask(1,id[u],id[u]+size[u]-1));
    	}
    }
    
    return 0;
}