Xor Path

题意：
有一棵n个节点的树，树的每一个节点有一个权值，定义path(i,j)表示 i 到 j 的最短路径上，所有点的点权异或和。求所有path(i,j)的异或和。

思路：
我们可以统计一个点被计算了多少次来求解，一个节点x，以x为终点的path有（n-1）条，然后包括它的路径与它的子树有关，一棵子树的节点到另一颗子树的节点路径包括x，节点数为偶数的不考虑，计算为奇数节点的个数，因为奇数 * 奇数才等于奇数。然后判断奇子树二二组合的数目，然后就将这值与n-1加起来是否为奇数，为奇数则ans异或x节点的权值，否则不管。

代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll inf=998244353;

vector<int> g[500005];
ll a[500005];

ll ans=0, n;

int dfs(int v,int f)
{
    ll p=1, ji=0;
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]!=f)
        {
            int k=dfs(g[v][i],v);
            if(k%2==1)
            {
                ji++;
            }
            p=p+k;
        }
    }
    if((n-p)%2==1)
    {
        ji++;
    }
    ji--;
    if(ji%4>=1&&ji%4<=2)
    {
        ji=1;
    }
    else
    {
        ji=0;
    }
    ans=ans^(a[v]*((n-1+ji)%2));
    return p;
}

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<n;i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    dfs(1,-1);
    cout << ans << endl;
    return 0;
}