CF888G Xor-MST BoruvkaTrie

发表于 更新于 分类于 阅读次数：

CF888G Xor-MST 求奇怪边权的MST，考虑Boruvka。 考虑第一次Boruvka的过程。每个点选最小边，合并。把所有点放在Trie上，则体现为叶子处的点合并。 合并叶子后，Trie产生了新的叶子，进行下一次Boruvka即可。 考虑Trie上一个点，可以计算合并它左右儿子的贡献。只需从左右儿子的集合中连一条最小边。这个可以在Trie上直接查询。

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
#include <bits/stdc++.h>

const int N = 2e5 + 233;

int n, A[N], ch[N * 40][2], tot;
int L[N], R[N];

inline void insert(int v, int id) {
  int x = 0;
  for (int i = 30; ~i; --i) {
    int t = (v >> i) & 1;
    if (!ch[x][t])
      ch[x][t] = ++tot;
    x = ch[x][t];
    L[x] = std::min(L[x], id);
    R[x] = std::max(R[x], id);
  }
}

inline int query(int x, int v, int d) {
  int ret = 0;
  for (int i = d; ~i; --i) {
    int t = (v >> i) & 1;
    if (ch[x][t])
      x = ch[x][t];
    else {
      x = ch[x][t ^ 1];
      ret = 1 << i;
    }
  }
  return ret;
}

long long solve(int x, int dep) {
  if (dep < 0) return 0;
  if (ch[x][0] && ch[x][1]) {
    int min = 2e9;
    for (int i = L[ch[x][0]]; i <= R[ch[x][0]]; ++i)
      min = std::min(min, query(ch[x][1], A[i], dep - 1));
    return solve(ch[x][0], dep - 1) + solve(ch[x][1], dep - 1)
      + min + (1 << dep);
  } else if (ch[x][0]) {
    return solve(ch[x][0], dep - 1);
  } else if (ch[x][1]) {
    return solve(ch[x][1], dep - 1);
  }
  return 0;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", A + i);
  std::sort(A + 1, A + n + 1);
  memset(L, 0x3f, sizeof(L));
  L[0] = 1, R[0] = n;
  for (int i = 1; i <= n; ++i)
    insert(A[i], i);
  printf("%lld\n", solve(0, 30));
  return 0;
}