记录编号	585425	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.360 s
提交时间	2023-12-09 20:47:46	内存使用	24.39 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 2e5+10;
int n,m;
struct made{
	int ver,nx;
}e[N<<1]; 
int hd[N],tot,cnt;
int fa[N],son[N],size[N],dep[N];
int top[N],dfn[N],rnk[N];
struct Tree{
	int l,r,sum,la;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define sum(x) t[x].sum
	#define la(x) t[x].la
}t[N<<2];
void pushdown(int x){
	if(la(x) == -1)return;
	la(x<<1) = la(x<<1|1) = la(x);
	sum(x<<1) = la(x) * (r(x<<1) - l(x<<1) + 1);
	sum(x<<1|1) = la(x) * (r(x<<1|1) - l(x<<1|1) + 1);
	la(x) = -1; 
}
void pushup(int x){
	sum(x) = sum(x<<1) + sum(x<<1|1);
}
void build(int x,int l,int r){
	l(x) = l,r(x) = r,la(x) = -1;
	if(l == r)return;
	int mid = l + r >> 1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}
void change(int x,int l,int r,int z){
	if(l <= l(x) && r(x) <= r){
		la(x) = z;
		sum(x) = z * (r(x) - l(x) + 1);
		return;
	}
	pushdown(x);
	int mid = l(x) + r(x) >> 1;
	if(l <= mid)change(x<<1,l,r,z);
	if(r > mid)change(x<<1|1,l,r,z);
	pushup(x);
}
//-------------------------
void add(int x,int y){
	tot++;
	e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
void dfs1(int x){
	size[x] = 1;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(dep[y])continue;
		dep[y] = dep[x] + 1;
		fa[y] = x;
		dfs1(y);
		size[x] += size[y];
		if(!son[x] || size[y] > size[son[x]])son[x] = y;
	}
}
void dfs2(int x,int t){
	dfn[x] = ++cnt;
	rnk[cnt] = x;
	top[x] = t;
	if(!son[x])return;
	dfs2(son[x],t);
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y != fa[x] && y != son[x])dfs2(y,y);
	}
}
void cal(int x,int y,int z){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]])swap(x,y);
		change(1,dfn[top[x]],dfn[x],z);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])swap(x,y);
	change(1,dfn[x],dfn[y],z);
}
int main(){
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	scanf("%d",&n);
	for(int i = 2;i <= n;i++){
		int x;
		scanf("%d",&x);x++;//从0节点开始
		add(i,x),add(x,i);
	}
	dep[1] = 1;
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	scanf("%d",&m);
	for(int i = 1;i <= m;i++){
		char c[10];int x,ans = 0;
		scanf("%s%d",c,&x);x++;//同上 
		ans = t[1].sum;
		if(c[0] == 'i')cal(1,x,1);
		else change(1,dfn[x],dfn[x]+size[x]-1,0);
		printf("%d\n",abs(ans-t[1].sum));
	}
	
	return 0;
	
}