NC20857 Xor Path
Xor Path
https://ac.nowcoder.com/acm/problem/20857
Xor Path
题目地址：
基本思路：
根据题意我们要找树中所有点权路径的异或和,
那我们考虑每个点的权值在什么情况下会被计算进去,
我们思考计算在所有最短路径中,经过顶点的次数,
如果经过了偶数次,那么很明显它会被自身抵消掉,否则它仍然存在,和其他也存在的顶点异或就行了。
那我们考虑如何计算每个点在最短路中的被计算计数,
相信如果这里是边,不是点,大家肯定就都会了,因为计算边的最短路经过次数是老套路了,
就是,
那么点的怎么计算,实际上我们只要计算和这个点相连的所有边的被计算次数加上(这个点自身和其他所有点)再除以
就行了,
因为如果经过和这个点相连边那么就一定也是经过这个点的,同时这个点自身出发的所有最短路也是经过这个点的。
但是这里和
会有一个重复计算,所以还要再除以二。
参考代码：
#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;
}