题目大意

定义 为树上编号为 两点路径上的点权异或和。求所有 的异或和。

题解

由于都是异或和，因此只需要对每一个点考虑其在所有路径中出现的次数即可。
将出现分成三个部分：点出现在其子树内点和外部点的路径上、点连接其子树内点的路径上、点出现在其子树内点之间的路径上。分别统计即可。
时间复杂度为 。可以一次 DFS 实现，我这里用了两次。

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[500005], siz[500005] = {0}, ans = 0;
int to[1000005], nxt[1000005], at[500005] = {0}, cnt = 0;
void dfs(int cur, int fa){
    siz[cur] = 1;
    for (int i = at[cur]; i; i = nxt[i]){
        int v = to[i];
        if (v == fa) continue;
        dfs(v, cur);
        siz[cur] += siz[v];
    }
}
void dfs2(int cur, int fa){
    int sum = (n - siz[cur]) & 1, sum2 = 0;
    sum = (sum * siz[cur]) & 1;
    sum = (sum + (siz[cur] - 1)) & 1;
    for (int i = at[cur]; i; i = nxt[i]){
        int v = to[i];
        if (v == fa) continue;
        sum = (sum + siz[v] * sum2) & 1;
        sum2 = (sum2 + siz[v]) & 1;
        dfs2(v, cur);
    }
    if (sum & 1) ans ^= a[cur];
}
void init(){
    n = read();
    REP(i, 1, n - 1){
        int u = read(), v = read();
        to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
        to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
    }
    REP(i, 1, n)
        a[i] = read();
}
void solve(){
    dfs(1, 0);
    dfs2(1, 0);
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}