有比较好想的 Trie 树做法。但是树上差分更巧妙。
从下往上做。从儿子继承到父亲，使得儿子内所有点到父亲的距离等于儿子内所有点到儿子的距离 $+1$，也就是全局 $+1$ 操作。并且维护的信息是异或和。类似于线段树合并，我们直接 01-Trie 合并即可。时间复杂度 $\mathcal O(n\log V)$。
换种思路，我们对于每一个 $v_i$ 分别考虑其对祖先的贡献。考虑整个 $+1$ 然后进位的过程，对于第 $k$ 位为 $1$，那么对它的祖先的第 $k$ 位贡献 $\underbrace{11\cdots 11}_{2^k-(v_i\text{ mod } 2^k)}\underbrace{00\cdots 00}_{2^k}\underbrace{11\cdots 11}_{2^k}$。根据这一点进行树上差分。给定差分数组 $g[x][i]$ 表示 $x$ 第 $i$ 位的差分。把当前 $v_i$ 每一位的差分往上传递到，把 $g[x][i]$ 的差分到 $g[fa_{x,2^i}][i]$。需要长链剖分求 $k$ 级祖先，时间复杂度 $\mathcal O(n\log n + n\log V)$。常数要小一点。
实际上有更好的实现方式。我们发现对于每个点，产生差分的点的充要条件是 $d_i=x\pmod {2^k}$。我们开一个新的 $p[k][x]$ 表示 $d_i=x\pmod {2^k}$ 的差分。递归之前先去掉已经原来的差分数组，再递归得到子树的贡献，再算出当前点的答案即可。时间复杂度 $\mathcal O(n\log V)$。常数很小。
具体实现参考如下。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=5.26e5+10,K=21;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int a[N],p[K][N];
int tot,head[N],ver[N<<1],ne[N<<1];
ll ans;
inline void add(int u,int v)
{
ver[++tot]=v;
ne[tot]=head[u];
head[u]=tot;
}
int dfs(int x,int d)
{
int res=a[x];
for(int i=0;i<K;i++)res^=p[i][d&((1<<i)-1)];
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
res^=dfs(y,d+1);
}
for(int i=0;i<K;i++)res^=p[i][d&((1<<i)-1)];
for(int i=0;i<K;i++)p[i][(d+a[x])&((1<<i)-1)]^=1<<i;
ans+=res;
return res;
}
int main()
{
read(n);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=2,fa;i<=n;i++)read(fa),add(fa,i);
dfs(1,0);
printf("%lld\n",ans);
return 0;
}
|