记录编号	568820	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	4.911 s
提交时间	2022-02-07 18:19:51	内存使用	11.11 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int head[maxn],ver[maxn],nxt[maxn],cnt;
void add(int u,int v) {
	ver[++ cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
	return ;
}
int n;
int f[maxn],son[maxn],size[maxn],d[maxn],top[maxn],id[maxn],rk[maxn];
void dfs1(int u) {
	size[u] = 1;
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i];
		if(v == f[u])continue ;
		d[v] = d[u] + 1;
		f[v] = u;
		dfs1(v);
		size[u] += size[v];
		if(size[son[u]] < size[v])son[u] = v;
	}
	return ;
}
void dfs2(int u,int tp) {
	top[rk[id[u] = ++ cnt] = u] = tp;
	if(!son[u])return ;
	dfs2(son[u] , tp);
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i];
		if(v == f[u]||v == son[u])continue ;
		dfs2(v , v);
	}
	return ;
}
int ls[maxn << 2],rs[maxn << 2],sum[maxn << 2];
int lz[maxn << 2];
void pushup(int i) {
	sum[i] = sum[i << 1] + sum[i << 1 | 1];
	return ;
}
void build(int i,int l,int r) {
	ls[i] = l;
	rs[i] = r;
	if(l == r) {
		sum[i] = 0;
		lz[i] = 0;
		return ;
	}
	int mid = l + r >> 1;
	build(i << 1 , l , mid);
	build(i << 1 | 1 , mid + 1 , r);
	pushup(i);
	return ;
}
void pushdown(int i) {
	if(!lz[i])return ;
	if(lz[i] & 1) {
		lz[i << 1] = lz[i << 1 | 1] = lz[i];
		sum[i << 1] = rs[i << 1] - ls[i << 1] + 1;
		sum[i << 1 | 1] = rs[i << 1 | 1] - ls[i << 1 | 1] + 1;
	}
	else {
		lz[i << 1] = lz[i << 1 | 1] = lz[i];
		sum[i << 1] = sum[i << 1 | 1] = 0;
	}
	lz[i] = 0;
	return ;
}
void modify(int i,int l,int r,int k) {
	if(ls[i] >= l&&rs[i] <= r) {
		lz[i] = k;
		if(k & 1)sum[i] = rs[i] - ls[i] + 1;
		else sum[i] = 0;
		return ;
	}
	if(ls[i] > r||rs[i] < l)return ;
	pushdown(i);
	int mid = ls[i] + rs[i] >> 1;
	if(l <= mid)modify(i << 1 , l , r , k);
	if(r > mid)modify(i << 1 | 1 , l , r , k);
	pushup(i);
	return ;
}
int query(int i,int l,int r) {
	if(ls[i] >= l&&rs[i] <= r) {
		return sum[i];
	}
	if(ls[i] > r||rs[i] < l)return 0;
	pushdown(i);
	int mid = ls[i] + rs[i] >> 1,s = 0;
	if(l <= mid)s += query(i << 1 , l , r);
	if(r > mid)s += query(i << 1 | 1 , l , r);
	return s;
}
int Modify(int x,int y,int k) {
	int ans = 0;
	while(top[x] != top[y]) {
		if(d[top[x]] < d[top[y]])swap(x , y);
		ans += id[x] - id[top[x]] + 1 - query(1 , id[top[x]] , id[x]);
		modify(1 , id[top[x]] , id[x] , k);
		x = f[top[x]];
	}
	if(id[x] > id[y])swap(x , y);
	ans += id[y] - id[x] + 1 - query(1 , id[x] , id[y]);
	modify(1 , id[x] , id[y] , k);
	return ans;
}
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;
		add(x , i);
	}
	dfs1(1);
	cnt = 0;
	dfs2(1 , 1);
	build(1 , 1 , n);
	int Q;
	scanf("%d",&Q);
	while(Q --) {
		char s[10];
		int x;
		scanf("%s%d",s + 1,&x);
		++ x;
		if(s[1] == 'i') {
			printf("%d\n",Modify(1 , x , 1));
		}
		else {
			printf("%d\n",query(1 , id[x] , id[x] + size[x] - 1));
			modify(1 , id[x] , id[x] + size[x] - 1 , 2);
		}
	}
	return 0;
}