题目

题目链接

「Codeforces Gym」102832F

题目大意

给出一棵有 $n(2\le n\le10^5)$ 个节点的树，对于节点 $i$，有权值 $a_i(1\le a_i\le10^6)$，求：

其中，$\oplus$ 表示按位异或

解题思路

  • 这道题我们很明显能想到一个启发式合并的做法，当我们把 $u$ 的子树 $v_i$ 往子树 $v_j$ 上合并时，遍历 $v_i$，设当前遍历到的节点为 $k$，判断 $a_u\oplus a_k$ 是否在子树 $v_j$ 中出现，然后统计答案即可
  • 这里我们考虑 $Dsu\ On\ Tree$ 的做法，每次保留重儿子所在的子树，然后把其他儿子所在的子树往该子树上合并，因为最终是求位置的异或和，所以我们把位置信息拆成 $20$ 位，按位统计
  • 时间复杂度：$O(n\log^2n)$

完整代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
#define ll long long

vector<int> vec[maxn];
unordered_map<int, array<array<int, 2>, 20>> dig;

int a[maxn];
int size[maxn], mson[maxn];
ll ans;

void update(int key, int val, int op) {
    for (int i = 0; i < 20; i++) dig[key][i][(val >> i) & 1] += op;
}

void add(int key, int val) {
    if (dig.find(key) == dig.end()) return;
    for (int i = 0; i < 20; i++)
        ans += (ll)dig[key][i][((val >> i) & 1) ^ 1] * (1 << i);
}

void dfs1(int u, int fa) {
    size[u] = 1;
    for (auto v : vec[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        if (size[v] > size[mson[u]]) mson[u] = v;
        size[u] += size[v];
    }
}

void count(int u, int fa, int rt) {
    add(a[u] ^ a[rt], u);
    for (auto v : vec[u])
        if (v != fa) count(v, u, rt);
}

void deal(int u, int fa, int op) {
    update(a[u], u, op);
    for (auto v : vec[u])
        if (v != fa) deal(v, u, op);
}

void dfs2(int u, int fa, bool del) {
    for (auto v : vec[u])
        if (v != mson[u] && v != fa) dfs2(v, u, true);
    if (mson[u]) dfs2(mson[u], u, false);

    update(a[u], u, 1);
    for (auto v : vec[u])
        if (v != fa && v != mson[u]) count(v, u, u), deal(v, u, 1);
    if (del) deal(u, fa, -1);
}

void Main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0, false);
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Main();
    return 0;
}