树dp 统计异或值

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

题目描述

给定一棵n个点的树，每个点有权值 ${A_i}$ 。定义 ${\mathbb{path}(i,j)}$ 表示

到

的最短路径上，所有点的点权异或和。

对于 ${i=1\sim n-1,\ j=i+1\sim n}$ ，求所有 ${\mathbb{path}(i,j)}$ 的异或和。

输入描述:

第一行一个整数n。

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

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

输出描述:

输出一个整数，表示所有

${\mathbb{path}(i,j)}$

的异或和，其中

${i=1\sim n-1,\ j=i+1\sim n}$

。

示例1

输入

复制

输出

复制

说明

${mathbb{path}(1,2)=A_1 mathbb{xor} A_2=3\ mathbb{path}(1,3)=A_1 mathbb{xor} A_3=2\ mathbb{path}(1,4)=A_1 mathbb{xor} A_4=5\ mathbb{path}(2,3)=A_2 mathbb{xor} A_1 mathbb{xor} A_3=0\ mathbb{path}(2,4)=A_2 mathbb{xor} A_1 mathbb{xor} A_4=7\ mathbb{path}(3,4)=A_3 mathbb{xor} A_1 mathbb{xor} A_4=6}$

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

备注:

${1\leq n\leq5\times10^5,0\leq A_i\leq10^9}$

。
题意：给你一棵树以及树上结点的权值，求任意两点间路径上点权值的异或，再将所有的路径异或起来。
思路分析 ：
　　通过边的方式去考虑，首先可以知道每条边会用多少次，然后就知道对应的点用了多少次，但是会有重复的
　　重复的部分就是借助某点任意两点间的部分，只要减去即可。即 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
", ans);
    return 0;
}