NC20857（Xor Path）

感受


思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e5 + 10;
struct edge{
    int v, nex;
}e[maxn << 1];
int num[maxn], head[maxn], cnt;
ll a[maxn];
int n;
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    for(int i = 1; i <= n; i++){
        head[i] = -1;
    }
}
ll ans;
void dfs(int u, int fa){
    int v;
    num[u] = 1; ll res = 0;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa) continue;
        dfs(v, u);
        num[u] += num[v];
    }
    ll sum = num[u];
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa) continue;
        sum -= num[v];
        res += (ll)1 * num[v] * sum;///一个节点在子树, 另外一个节点在子树(包括u)
    }
    res += (ll)1 * (num[u] - 1) * (n - num[u]);///一个节点在子树, 一个在u的上方
    res = res + n - num[u];///一个节点在u, 一个节点在u的上方
    if(res & 1){
        ans ^= a[u];
    }
}
int main(){
    //printf("%d\n", 1 << 30);
    scanf("%d", &n);
    init();
    int u, v;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}