[Nowcoder272B] Xor Path(树，异或，计数)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://ac.nowcoder.com/acm/contest/272/B

给定一棵n个点的树，每个点有权值$A_i$. 定义$path(i,j)$表示$i$到$j$的最短路径上，所有点的点权异或和。对于$i=1\to n-1,j=i+1 \to n$，求所有$path(i,j)$的异或和。

考虑到这个问题只和每个点权的出现次数的奇偶有关系，那么我们可以分情况讨论下每个点在任意两点间的路径中都是如何出现的。

  • 对于叶子节点，只有n-1次（与其他点直连）。
  • 对于非叶节点，则有：
    • 与其他点直连，出现n-1次。
    • 这个点的子树中的任意两点进行连接，出现$\sum_{1\leq i<j\leq n} child_i\times child_j$次，其中$child_i$表示第$i$个儿子为根节点的总点数（包括自己）。
    • 这个点将子树和非子树分成两部分，这两部分互相连接。那么贡献是两部分点数的乘积。

只有一个地方的计算需要优化，那就是$k$个数任意取2个数的乘积之和，维护一个前缀和随便弄一下就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
 
using LL = long long;
const int maxn = 500500;
int n;
LL w[maxn], son[maxn], cnt[maxn];
LL out[maxn];
vector<int> G[maxn];
 
void dfs(int u, int p) {
  son[u] = 1;
  int tot = 0;
  vector<int> sum, val;
  for(auto v : G[u]) {
    if(v == p) continue;
    dfs(v, u);
    son[u] += son[v];
    sum.emplace_back(son[v]);
    val.emplace_back(son[v]);
    tot++;
  }
  for(int i = 1; i < tot; i++) {
    sum[i] += sum[i-1];
  }
  for(int i = 0; i < tot; i++) {
    out[u] += ((val[i] * (sum[tot-1] - sum[i]))) % 2;
    out[u] %= 2;
  }
}
 
signed main() {
  // freopen("in", "r", stdin);
  int u, v;
  while(~scanf("%d", &n)) {
    for(int i = 1; i <= n; i++) {
      G[i].clear();
    }
    memset(cnt, 0, sizeof cnt);
    memset(out, 0, sizeof out);
    memset(son, 0, sizeof son);
    for(int i = 1; i < n; i++) {
      scanf("%d%d",&u,&v);
      G[u].emplace_back(v);
      G[v].emplace_back(u);
    }
    for(int i = 1; i <= n; i++) {
      scanf("%lld", &w[i]);
    }
    dfs(1, -1);
    LL ret = 0;
    for(int i = 1; i <= n; i++) {
      cnt[i] = (n - 1) % 2;
      cnt[i] += ((son[i] - 1) * (n - son[i])) % 2;
      cnt[i] += out[i] % 2;
      cnt[i] %= 2;
      if(cnt[i] & 1) ret ^= w[i];
    }
    printf("%lld\n", ret);
  }
  return 0;
}