黄队的宫殿

题目描述
宫殿共由 /(n/) 个洞穴和 /(n−1/) 条通路组成。对于第 /(i/) 个洞穴，我们将它编号为 /(i/)。黄队在创造地下宫殿的时候，对于所有编号大于等于 /(2/) 的洞穴，都在它和编号比它小的某个洞穴之间建造了一条通路。具体来说，对于所有 /(2≤i≤n/)，黄队会选定一个正整数 /(a_i/)，满足 /(1≤a_i≤i−1/)，并添加一条连接第 /(i/) 个洞穴和第 /(a_i/) 个洞穴的通路。

此外，每一个宫殿里都有一盏灯和一个开关，一开始所有灯都是熄灭的。如果按动第 /(i/)个洞穴的开关，这个洞穴的灯的状态会改变。也就是说：如果灯原来是灭的，那么现在把它点亮；如果它原来是亮的，那么现在把它熄灭。除此以外，与这个洞穴相邻的所有洞穴里的灯的状态也会改变。我们称两个洞穴相邻，当且仅当它们之间存在一条直接通路。注意到一个开关可以按动多次，每次按动都会对灯造成影响。

现在黄队会告诉你宫殿的形态，理所应当地，你也需要回馈黄队一些东西。黄队要求你帮他写「NOI 2019」I 君的探险 一题的交互库。当然，如果你看不懂上面一句话也没关系。现在有一个叫 I 君的旅行者进入了洞穴。他会进行 /(m/) 次操作，每次操作时他会告知你一个参数 /(x/)，操作分为两种：

操作 1：旅行者按动了编号为 /(x/) 的洞穴里的开关。关于开关的叙述可以在第二自然段中找到。
操作 2：旅行者想知道与当前编号为 /(x/) 的洞穴以及与之相邻的所有洞穴中亮着的灯的总数。
你要写一个程序，正确地回答旅行者的问题。

输入输出格式
输入格式
第一行一个数 /(n/)。

第二行 /(n−1/) 个数，第 /(i/) 个数是 /(a_{i+1}/)。

第三行一个数 /(m/)。

接下来 /(m/) 行，每行两个数 /(t,x/)，/(t/) 表示操作类型，/(x/) 表示旅行者给定的参数。

输出格式
对于每个 /(t=2/) 的操作，输出一个数，表示旅行者问题的答案。

样例
样例 #1

5
1 1 2 2
8
2 3
1 1
1 3
2 5
1 2
2 2
1 5
2 4

0
1
3
2

样例解释

宫殿共有 5 个结点和 4 条通路，分别连接$ (1,2),(1,3),(2,4),(2,5)$ 这 4 对洞穴。

一开始，每个洞穴里的灯都是熄灭的。
对于第$ 1$ 个操作，没有洞穴的灯是亮着的，所以答案为 0。
第$ 2$ 个操作过后，洞穴 /(1,2,3/) 的灯由暗变亮。
第 /(3/) 个操作过后，洞穴$ 1,3$ 的灯由亮变暗。
对于第 /(4/) 个操作，只有洞穴 /(2/) 是亮着的，所以答案为 /(1/)
第 /(5/) 个操作过后，洞穴 /(1,4,5/) 的灯由暗变亮，洞穴 /(2/) 的灯由亮变暗。
对于第 /(6/) 个操作，洞穴 /(1,4,5/) 是亮着的，所以答案为 /(3/)。
第 /(7/) 个操作过后，洞穴 /(2/) 的灯由暗变亮，洞穴 /(5/) 的灯由亮变暗。
对于第 /(8/) 个操作，洞穴 /(2,4/) 是亮着的，所以答案为 /(2/)。注意到洞穴 /(1/) 也是亮着的，但是它不和 /(4/) 号洞穴相邻，所以不计算进答案。

限制与约定
数据保证
对于 20% 的数据，/(n≤100,m≤10^4/)。

对于 30% 的数据，所有操作中的 /(x/) 随机生成。

另有 10% 的数据，/(a_i=1(2≤i≤n)/)。

对于 70% 的数据，所有 /(t=2/) 的操作中的 /(x/) 随机生成。

另有 10% 的数据，所有 /(t=1/) 的操作都出现在 /(t=2/) 操作的前面。

对于 100% 的数据，/(1≤n,m≤10^6/)。

对于所有数据，有 /(1≤t≤2,1≤x≤n,1≤a_i≤i−1(2≤i≤n)/)。

注意：我们并不保证 /(a_i/) 随机。

时空限制
时间限制：3s。

空间限制：512MB。

这题有一个很重要的特点就是给出的是一棵树。也就是说，他只有一个父亲。所以其实我们把需要询问和修改的点分成三部分：自己，父亲和儿子。自己和父亲暴力改，儿子的改变记到自己身上，询问儿子的时候加上他的父亲对他的影响。这就是大概的思路。

因为他的开/关是他的儿子，他自己和他的父亲的影响共同造成的。他的儿子时直接修改，他自己改时也直接修改。每个点记录下他对他儿子的修改，那么一个点的值还要加上他的父亲对他的影响，就完成了。

但其实这样只能获得70分的数据。我们还需要对其统计一下有多少儿子异或上他对儿子的影响后为1。维护他的儿子除他对儿子的影响外的值/(x/)，然后看他是否对儿子进行影响，如果有，就用儿子个数减去x，否则输出x，还要加上他自己和父亲。

注意特判根节点。

#include<cstdio>
const int N=1e6+5;
int n,a[N],m,p[N],v[N],hd[N],x,op,ret,s[N],t[N];
struct edge{
	int v,nxt;
}e[N];
void add_edge(int u,int v)
{
	e[v]=(edge){v,hd[u]};
	hd[u]=v;
}
inline void turn(int x)
{
	if(p[x])
		--s[a[x]];
	else
		++s[a[x]];
	p[x]^=1;
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&a[i]),t[a[i]]++;
		add_edge(a[i],i);
	}
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d%d",&op,&x);
		if(op==1)
		{
			turn(x);
			turn(a[x]);
			v[x]^=1;
		}
		else
		{
			ret=(p[x]^v[a[x]]);
			if(x!=1)
				ret+=(p[a[x]]^v[a[a[x]]]);
			if(!v[x])
				ret+=s[x];
			else
				ret+=t[x]-s[x];
			printf("%d/n",ret);
		}
	}
}