原题传送门
考虑一个点上的数对整体产生的贡献
因为是亦或,考虑某个数每个位对整体产生的贡献
加入一个点上的数为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
2^2
22,每个循环节中,0/1重复
2
1
2^1
21次,对于这一位数值为1的那
2
1
2^1
21个数我是可以产生
x
o
r
2
1
xor2^1
xor21的贡献
推而广之
第k位,01的循环节长度为
2
k
+
1
2^{k+1}
2k+1,每个循环节中,0/1重复
2
k
2^k
2k次,对于这一位数值为1的那
2
k
2^k
2k个数我是可以产生
x
o
r
2
k
xor2^k
xor2k的贡献
所以可以树上差分,对于每一位,每个循环节中第一个
1
1
1的位置亦或上
2
k
2^k
2k,第一个
0
0
0的位置也亦或上
2
k
2^k
2k,表示一段值为
1
1
1的区间可以亦或上
2
k
2^k
2k
然后继续优化这个差分,发现要改变的差分数组的下标
i
i
i,对于第
k
k
k位,总满足
i
mod
2
k
=
0
i\text{ mod }2^k=0
i mod 2k=0即
i
and
(
2
k
−
1
)
=
0
i\text{ and }(2^k-1)=0
i and (2k−1)=0
对于一个点,要找出自己的哪些祖先可以被亦或,可以用深度来刻画
如果自己的权值
a
u
a_u
au,加上祖先和自己的深度差
d
e
l
t
a
d
delta_d
deltad,即
a
u
+
d
e
l
t
a
d
a_u+delta_d
au+deltad就是上面说的
i
i
i,但是在
d
f
s
dfs
dfs过程中,每次只能弄“跟自己有关的”,转化为
a
u
+
d
u
与
d
v
对
于
2
k
同
余
a_u+d_u与d_v对于2^k同余
au+du与dv对于2k同余,其中
v
v
v是
u
u
u的祖先
这样子树上差分就是
O
(
n
l
o
g
n
)
O(nlogn)
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;
}