Xor Path_牛客博客

题目描述

给定一棵n个点的树，每个点有权值 ${A_i}$ 。定义 ${\mathbb{path}(i,j)}$ 表示 ${i}$ 到 ${j}$ 的最短路径上，所有点的点权异或和。
对于 ${i=1\sim n-1,\ j=i+1\sim n}$ ，求所有 ${\mathbb{path}(i,j)}$ 的异或和。

输入描述:

第一行一个整数n。
接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。
第n+1行有n个整数，表示每个点的权值 ${A_i}$ 。

输出描述:

输出一个整数，表示所有 ${\mathbb{path}(i,j)}$ 的异或和，其中 ${i=1\sim n-1,\ j=i+1\sim n}$ 。

题解

直接求复杂度肯定接受不了，我们考虑计算对答案的贡献

由于一个数异或它本身为0，所以偶数次异或本身为0，奇数次异或本身等于数字本身。

对于一棵树，两个节点间的最短路唯一，对于任意 ${\mathbb{path}(i,j)}$ ，我们设 ${b[x]}$ 为根节点到x节点的路径权值异或和，那么 ${\mathbb{path}(i,j)}={b[i]}\otimes{b[j]}\otimes{a[lca(i,j)]}$ 。

${b[i]}\otimes{b[j]}$ 之后，从根节点到到两节点的 ${lca}$ 的路径被计算了两次，异或之后影响消除，但是少计算了其 ${lca}$ 节点的权值。

最终答案又是所有 ${\mathbb{path}(i,j)}$ 异或起来，相当于每个 ${b[i]}$ 都会出现n-1次，所以关于b[i]的部分就很好统计了

接下来我们需要统计的就是 ${a[lca(i,j)]}$ 出现的次数，利用dfs去统计就好

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+100;
const int mod=1e9+7;

ll b[N],a[N],n,siz[N],ans=0;

vector<int> v[N];

void dfs(int node,int fa,ll w){
    b[node]=a[node]^w;
    siz[node]=1;
    ll res=0;
    for(int i=0,len=v[node].size();i<len;++i){
        int to=v[node][i];
        if(to==fa)continue;
        dfs(to,node,a[node]^w);
        res+=siz[node]*siz[to];
        siz[node]+=siz[to];
    }
    if(res&1)ans^=a[node];
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<n;++i){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    dfs(1,1,0);
    if(n%2==0){
        for(int i=1;i<=n;++i){
            ans^=b[i];
        }
    }
    cout<<ans<<endl;
}