Xor Path

题目描述

给定一棵n个点的树，每个点有权值。定义表示 到 的最短路径上，所有点的点权异或和。
对于，求所有的异或和。

输入描述:

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

输出描述:

输出一个整数，表示所有的异或和，其中。

题解

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

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

对于一棵树，两个节点间的最短路唯一，对于任意，我们设为根节点到x节点的路径权值异或和，那么。

之后，从根节点到到两节点的的路径被计算了两次，异或之后影响消除，但是少计算了其节点的权值。

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

接下来我们需要统计的就是出现的次数，利用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;
}