【每日一题】7月30日题目精讲—Xor Path

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<bits/stdc++.h>
typedef long long ll;
ll gcd(ll a, ll b)
{
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
	return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)		//快速幂模板
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = (ll)res * a % p;
		k >>= 1;
		a = (ll)a * a % p;
	}
	return res;
}
///////////////////////////////////////////////////////////
vector<int> a[N];
long long b[N], p[N], ans = 0;
int n;
void dfs(int x, int y) {
	p[x] = 1;
	long long sign = n - 1;
	for (int i = 0; i < a[x].size(); i++) {
		int son = a[x][i];
		if (son == y)
			continue;
		dfs(son, x);
		sign += p[son] * (n - p[son]);
		p[x] += p[son];
	}
	sign += p[x] * (n - p[x]);
	sign = sign / 2;
	if (sign % 2)
		ans ^= b[x];
}
int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	dfs(1, 0);
	cout << ans << endl;
	return 0;
}