Xor Path

题目地址：

https://ac.nowcoder.com/acm/problem/20857

基本思路：

根据题意我们要找树中所有点权路径的异或和,
那我们考虑每个点的权值在什么情况下会被计算进去,
我们思考计算在所有最短路径中,经过顶点的次数,
如果经过了偶数次,那么很明显它会被自身抵消掉,否则它仍然存在,和其他也存在的顶点异或就行了。
那我们考虑如何计算每个点在最短路中的被计算计数,
相信如果这里是边,不是点,大家肯定就都会了,因为计算边的最短路经过次数是老套路了,
就是,
那么点的怎么计算,实际上我们只要计算和这个点相连的所有边的被计算次数加上(这个点自身和其他所有点)再除以就行了,
因为如果经过和这个点相连边那么就一定也是经过这个点的,同时这个点自身出发的所有最短路也是经过这个点的。
但是这里和 会有一个重复计算,所以还要再除以二。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 5e5 + 5;
struct Edge{
    int to,next;
}edge[maxn << 1];
int cnt = 0,head[maxn];
void add_edge(int u,int v) {
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  head[u] = cnt;
}
int n,w[maxn],sz[maxn],ans = 0;
void dfs(int u,int par) {
  sz[u] = 1;
  int num = n - 1; // 从该点出发的最短路条数;
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == par) continue;
    dfs(to, u);
    num += (n - sz[to]) * sz[to]; // u -> to边的被经过次数;
    sz[u] += sz[to];
  }
  num += sz[u] * (n - sz[u]); // par -> u 边被经过次数;
  num /= 2; // 有重复要除二;
  if (num % 2) ans ^= w[u]; //如果为奇数,那么未被抵消;
}
signed main() {
  IO;
  n = read();
  mset(head, -1);
  rep(i, 1, n - 1) {
    int u = read(), v = read();
    add_edge(u, v);
    add_edge(v, u);
  }
  rep(i, 1, n) w[i] = read();
  dfs(1, 0);
  cout << ans << '\n';
  return 0;
}