每日一题 7月30日Xor Path 树上路径异或

题目链接：https://ac.nowcoder.com/acm/problem/20857

思路：我们考虑每个点的经过次数就可以了。
1：u到其他所有点 n-1
2：u的子树之间
3：u的子树到除u的其他点（父节点以上）

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

vector<int> G[500005];
int a[500005];
LL siz[500005];
int n, ans=0;
void DFS(int u, int fa) {

    LL sum=n-1;//1
    for(auto to: G[u]) {
        if(to!=fa) {
            DFS(to, u);
            sum+=siz[u]*siz[to];//2
            siz[u]+=siz[to];
        }
    }

    sum+=siz[u]*(n-siz[u]-1);//3
    siz[u]++;
    if(sum%2) {
        ans^=a[u];
    }
}

int main() {

    int x, y;
    scanf("%d", &n);
    for(int i=1; i<n; i++) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
    }
    DFS(1, 0);
    printf("%d\n", ans);

    return 0;
}