题意： 给定一棵个点的树，每个点有点权，问树上所有两点之间的最短路径异或和为多少，即求树上所有两点的路径所经过的点的点权的异惑和。
题解：
既然是考虑异或和，那么就要考虑一个点是否对答案有贡献。
考虑一个点在所有路径中出现的次数，由异或的性质，可以知道当一个点在所有路径中出现总次数为偶数时，则对答案无贡献。
对于树上任意一点，考虑这个点的路径计算：

  • 当这个点作为一条路径的端点时，共次。
  • 考虑这个点的所有子树中的两点路径经过该点的次数
  • 考虑这个点的子树与这个点的父亲结点除子树外的其他子树之间的路径经过该点的次数
    设共有个子结点，则答案为

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10, M = N << 1;
int q[N], n, res;
int h[N], e[M], ne[M], idx;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int siz[N];
void dfs(int u, int fa) {
    siz[u] = 1;
    int cnt = n - 1;
    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if(v == fa) continue;
        dfs(v, u);
        cnt += siz[v] * (siz[u] - 1);
        siz[u] += siz[v];
    }
    cnt += (siz[u] - 1) * (n - siz[u]);
    if(cnt & 1) res ^= q[u];
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        int a, b; scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    for(int i = 1; i <= n; i++) scanf("%d", &q[i]);

    dfs(1, 0);

    printf("%d\n", res);
}