【题解】LuoGu6623：[省选联考 2020 A 卷] 树

原题传送门
考虑一个点上的数对整体产生的贡献
因为是亦或，考虑某个数每个位对整体产生的贡献
加入一个点上的数为3，把这个3，以及它对祖先的贡献形式写出来
位数从右往左为0123……
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
单独取出第1位二进制数，发现是有规律的：1001100110011……
第1位，01的循环节长度为$2^2$，每个循环节中，0/1重复$2^1$次，对于这一位数值为1的那$2^1$个数我是可以产生$xor{2}^1$的贡献
推而广之
第k位，01的循环节长度为$2^{k+1}$，每个循环节中，0/1重复$2^k$次，对于这一位数值为1的那$2^k$个数我是可以产生$xor{2}^k$的贡献
所以可以树上差分，对于每一位，每个循环节中第一个$1$的位置亦或上$2^k$，第一个$0$的位置也亦或上$2^k$，表示一段值为$1$的区间可以亦或上$2^k$
然后继续优化这个差分，发现要改变的差分数组的下标$i$，对于第$k$位，总满足$i\text{ mod }{2}^k=0$即$i\text{ and }(2^k-1)=0$
对于一个点，要找出自己的哪些祖先可以被亦或，可以用深度来刻画
如果自己的权值$a_u$，加上祖先和自己的深度差$delt{a}_d$，即$a_u+delt{a}_d$就是上面说的$i$，但是在$dfs$过程中，每次只能弄“跟自己有关的”，转化为$a_u+d_u与d_v对于2^k同余$,其中$v$是$u$的祖先
这样子树上差分就是$O(nlogn)$

Code：

#include <bits/stdc++.h>
#define maxn 1000010
#define maxm 25
using namespace std;
long long ans;
struct Edge{
	int to, next;
}edge[maxn];
int num, head[maxn], a[maxn], val[25][maxn], n, power[25];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }

int dfs(int u, int d){
	int s = a[u];
	for (int i = 0; i <= 20; ++i) val[i][(d + a[u]) & (power[i] - 1)] ^= power[i];
	for (int i = 0; i <= 20; ++i) s ^= val[i][d & (power[i] - 1)];
	for (int i = head[u]; i; i = edge[i].next) s ^= dfs(edge[i].to, d + 1);
	for (int i = 0; i <= 20; ++i) s ^= val[i][d & (power[i] - 1)];
	ans += s;
	return s;
}

int main(){
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 2; i <= n; ++i) addedge(read(), i);
	power[0] = 1;
	for (int i = 1; i <= 20; ++i) power[i] = power[i - 1] << 1;
	dfs(1, 0);
	printf("%lld\n", ans);
	return 0;
}