CF888G Xor-MST DFS 生成树 Trie

Xor-MST

传送门

题面翻译

• 给定 $n$ 个结点的无向完全图。每个点有一个点权为 $a_i$。连接 $i$ 号结点和 $j$ 号结点的边的边权为 $a_i\oplus a_j$。
• 求这个图的 MST 的权值。
• $1\le n\le 2\times 10^5$，$0\le a_i<2^{30}$。

题目描述

You are given a complete undirected graph with $n$ vertices. A number $a_i$ is assigned to each vertex, and the weight of an edge between vertices $i$ and $j$ is equal to $a_{i}xor{a}_j$ .

Calculate the weight of the minimum spanning tree in this graph.

输入格式

The first line contains $n$ ( $1<=n<=200000$ ) — the number of vertices in the graph.

The second line contains $n$ integers $a_1$ , $a_2$ , …, $a_n$ ( $0<=a_i<2^{30}$ ) — the numbers assigned to the vertices.

输出格式

Print one number — the weight of the minimum spanning tree in the graph.

样例 #1

样例输入 #1

5
1 2 3 4 5

样例输出 #1

8

样例 #2

样例输入 #2

4
1 2 3 4

样例输出 #2

8

$以上来自洛谷$

解题思路

先讲一种算法：当前每个集合伸出去一条最短的边，然后把联通块缩成一个新的集合，用这种思想处理 $MST$。（学习 $MST$ 看这里）
但是如果我们要使得异或和最小，这个很容易想到 $01Trie$（学习 $Trie$ 树看这里），考虑将每一个点按照权值插到 $Trie$ 中，这样我们考虑叶子节点就是实际存在的点，而非叶子节点一定时若干对叶子节点的 $LCA$。（不知道 $LCA$？看这里）
根据二进制的性质，不难发现我们先合并 $LCA$ 深度大的点对更优，这样我们考虑 $\mathrm{dfs}$ 整个 $Trie$，对于一个非叶子节点，我们枚举他的 $0/1$ 子树的所有儿子，然后在 $1/0$ 子树中找到边权最小的来合并，如果我们从小到大插入，那么编号就是连续的，然后启发式合并即可。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 6e6 + 5;
int n, a[Maxn];
int rt, L[Maxn], R[Maxn], ch[Maxn][2], tot;
inline void Insert(int &now, int x, int dep) {
	if (!now) {
		now = ++tot;
	}
	L[now] = min(L[now], x), R[now] = max(R[now], x);
	if (dep < 0) {
		return;
	}
	int bit = a[x] >> dep & 1;
	Insert(ch[now][bit], x, dep - 1);
}
inline int query(int now, int val, int dep) {
	if (dep < 0) {
		return 0;
	}
	int bit = val >> dep & 1;
	if (ch[now][bit]) {
		return query(ch[now][bit], val, dep - 1);
	} else {
		return query(ch[now][bit ^ 1], val, dep - 1) + (1 << dep);
	}
}
inline int dfs(int now, int dep) {
	if (dep < 0) {
		return 0;
	}
	if (R[ch[now][0]] && R[ch[now][1]]) {
		int minn = INT_MAX;
		for (int i = L[ch[now][0]]; i <= R[ch[now][0]]; i++) {
			minn = min(minn, query(ch[now][1], a[i], dep - 1));
		}
		return dfs(ch[now][0], dep - 1) + dfs(ch[now][1], dep - 1) + minn + (1 << dep);
	}
	if (R[ch[now][0]]) {
		return dfs(ch[now][0], dep - 1);
	}
	if (R[ch[now][1]]) {
		return dfs(ch[now][1], dep - 1);
	}
	return 0;
}
inline void work() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	memset(L, 0x3f, sizeof(L));
	for (int i = 1; i <= n; i++) {
		Insert(rt, i, 30);
	}
	cout << dfs(rt, 30) << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}