树dp 统计异或值

链接：https://ac.nowcoder.com/acm/contest/272/B
来源：牛客网

题目描述

给定一棵n个点的树，每个点有权值。定义表示  到  的最短路径上，所有点的点权异或和。

对于，求所有的异或和。

输入描述:

第一行一个整数n。

接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。

第n+1行有n个整数，表示每个点的权值。

输出描述:

输出一个整数，表示所有

的异或和，其中

。

示例1

输入

4

1 2

1 3

1 4

1 2 3 4

输出

5

说明

再将这6个数异或起来就可以得到答案5了。

备注:

。
题意：给你一棵树以及树上结点的权值，求任意两点间路径上点权值的异或，再将所有的路径异或起来。
思路分析 ：
　　通过边的方式去考虑，首先可以知道每条边会用多少次，然后就知道对应的点用了多少次，但是会有重复的
　　重复的部分就是借助某点任意两点间的部分，只要减去即可。即 cnt[x] = cnt[x] - (cnt[x]-(n-1))/2;
代码示例：

using namespace std;

#define ll long long

const ll maxn = 5e5+5;

const ll mod = 1e9+7;

const double eps = 1e-9;

const double pi = acos(-1.0);

const ll inf = 0x3f3f3f3f;

ll n;

vector<ll>ve[maxn];

ll size[maxn];

ll a[maxn];

ll cnt[maxn];

void dfs_init(ll x, ll fa){

    size[x] = 1;

    for(ll i = 0; i < ve[x].size(); i++){

        ll to = ve[x][i];

        if (to == fa) continue;

        dfs_init(to, x);

        size[x] += size[to];

    }

}

ll ans = 0;

void dfs(ll x, ll fa){

    for(ll i = 0; i < ve[x].size(); i++){

        ll to = ve[x][i];

        if (to == fa) continue;

        ll num = size[to]*(n-size[to]);

        cnt[x] += num, cnt[to] += num;

        dfs(to, x);

    }

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    ll u, v;

    cin >> n;

    for(ll i = 1; i < n; i++){

        scanf("%lld%lld", &u, &v);

        ve[u].push_back(v);

        ve[v].push_back(u);

    }

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

    dfs_init(1, 0);

    dfs(1, 0);

    for(ll i = 1; i <= n; i++){

        cnt[i] = cnt[i]-(cnt[i]-n+1)/2;

        if (cnt[i]&1) ans ^= a[i];

    }

    printf("%lld\n", ans);

    return 0;

}