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

· · 题解

首先，我们要求的是一个子树和状物体，那么就可以先考虑一个点，对于它的所有祖先的答案的贡献。

首先考察 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 呢？一种简单的想法是使用树上差分，在第

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)

上述题解提供的是基础思路，具体的计算和实现可以看代码。

本做法因为只使用了树上差分而没有使用高级数据结构，所以常数很小。

#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;
}