题解 P6623 【[省选联考 2020 A 卷] 树】
dengyaotriangle
2020-06-24 17:07:43
首先，我们要求的是一个子树和状物体，那么就可以先考虑一个点，对于它的所有祖先的答案的贡献。
首先考察 $c,c+1,c+2,\cdots$ 的二进制表示。
随便选一个 $c$，就比如说 $c=3$：
那么 $c,c+1,c+2,\cdots$ 的二进制表示就是：
$$\begin{matrix}+0&=&0011\\+1&=&0100\\+2&=&0101\\+3&=&0110\\+4&=&0111\\+5&=&1000\\+6&=&1001\\+7&=&1010\\+8&=&1011\\+9&=&1100\\\cdots&\cdots&\cdots\end{matrix}$$
我们随便找一位来看，比如说第二低的位：
$$\begin{matrix}+0&=&00{\color{red}1}1\\+1&=&01{\color{red}0}0\\+2&=&01{\color{red}0}1\\+3&=&01{\color{red}1}0\\+4&=&01{\color{red}1}1\\+5&=&10{\color{red}0}0\\+6&=&10{\color{red}0}1\\+7&=&10{\color{red}1}0\\+8&=&10{\color{red}1}1\\+9&=&11{\color{red}0}0\\\cdots&\cdots&\cdots\end{matrix}$$
按顺序串起来是 $1001100110\cdots$，我们发现，这是以 $0011$ 为循环节的串。
进一步地观察上方表格其它列，我们发现，第 $k$ 低位组成的01串的循环节长度是 $2^{k+1}$，是 $\underbrace{00\cdots0}_{2^k\text{个}}\underbrace{11\cdots 1}_{2^k\text{个}}$
我们考虑对于每一位分别计算贡献。那么，根据题面，对于每一位，它对它的 $0,1,2,\cdots$ 级祖先的贡献，就依次是上面表格中的那一列的值。
而我们要求的是每一个点的异或和，所以说其实对于第 $k$ 位，就是相当于把它的第
$$\begin{matrix}[0\times2^{k+1}+a,0\times2^{k+1}+a+2^k)\cup\\ [1\times2^{k+1}+a,1\times2^{k+1}+a+2^k)\cup\\ [2\times2^{k+1}+a,2\times 2^{k+1}+a+2^k)\cup\\\cdots\end{matrix}$$
级祖先的答案异或上 $2^k$
上面的那些区间可以很容易地根据我们之前找到的规律求出来，（循环节是 $2^{k+1}$，其中有 $2^k$ 个$1$）
而那个 $a$，代表的是一个循环节中的 $\cdots0000{\color{red}1}11\cdots$ 的那个 $\color{red}1$ 的位置。它也可以经过简单的数学推导或者看上面的表格找规律，使用位运算求得。
但怎么维护把上述那么多区间全异或上 $2^k$ 呢？一种简单的想法是使用树上差分，在第
$$\begin{matrix}
0\times2^k+a&1\times2^k+a\\2\times2^k+a&3\times2^k+a\\4\times2^k+a&5\times2^k+a\\\cdots&\cdots\end{matrix}$$
级祖先的差分数组上均异或上 $2^k$，就可以了，这样就可以保证在进入区间的时候答案异或 $2^k$，出区间时再异或回去。
但是我们有这么多的区间，树上差分依然是 $O(n^2)$ 的
但是，观察到，所有要异或 $2^k$ 的差分数组，它们的下标 $\mod 2^k$ 都一样，这就意味着，我们可以开一个新的差分数组，$s_{k,i}$，它等于所有当前dfs到的，深度 $d\mod 2^k=i$ 的所有的点的差分数组。
大概是这样（好丑）↑
那么，我们发现，我们修改的那很多的差分，就是单独地改了一个 $s_{k,a}$，这样就是 $O(1)$ 的了
但是怎么找到一个点的差分值呢？我们发现，它的差分值，就等于进入这个点的子树前的 $s_{k,d}$ （$d$为该点深度） 与出该点子树后的 $s_{k,d}$ 的异或差（其实就是异或和）
原因见下图。
因为我们一个点的差分，就是其子树内的点对于 $s_{k,d}$ 的修改，而这样做差刚好就只算了子树内贡献，所以是对的。
所以，我们对于每一个节点的每一位，都可以 $O(1)$ 地计算贡献和差分数组，所以总复杂度 $O(n\log n)$
上述题解提供的是基础思路，具体的计算和实现可以看代码。
本做法因为只使用了树上差分而没有使用高级数据结构，所以常数很小。
```cpp
#include<bits/stdc++.h>
using namespace std;
//dengyaotriangle!
const int maxl=21;
const int maxn=1<<maxl;
int n;
unsigned a[maxn];
vector<int> adj[maxn];
unsigned w[maxl][maxn];
unsigned long long tans=0;
unsigned dfs(int u,unsigned d){
unsigned ans=a[u];
for(int j=0;j<maxl;j++)w[j][(d+a[u])&((1u<<j)-1u)]^=1u<<j;
for(int j=0;j<maxl;j++)ans^=w[j][d&((1u<<j)-1u)];
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
ans^=dfs(v,d+1);
}
for(int j=0;j<maxl;j++)ans^=w[j][d&((1u<<j)-1u)];
//cerr<<u<<' '<<ans<<endl;
tans+=ans;
return ans;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i++){
int f;cin>>f;
adj[f].push_back(i);
}
dfs(1,0);
cout<<tans;
return 0;
}
```