题面

给定 $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}$ 。

题解

点权 01 Trie 中，权值最小的边明显是 LCA 最深的两点的边，易知有 $(n-1)$ 个结点有两个儿子，这 $(n−1)$ 个节点是一些在 Trie 中结尾结点的 LCA。

那么遍历 Trie，对于 LCA 点找一条最小的边把它的两棵子树合并。

代码

const int N = 2e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	ll a[N];
	int ch[N * 32][2], l[N * 32], r[N * 32], root, tot;
	void Insert (int &k, int id, int dep) {
		if (!k) k = ++tot;
		if (!l[k]) l[k] = id; r[k] = id;
		if (dep == -1) return;
		Insert (ch[k][(a[id] >> dep) & 1], id, dep - 1);
	}
	ll Query (int k, ll x, int dep) {
		if (dep == -1) return 0;
		int dig = (x >> dep) & 1;
		if (ch[k][dig]) return Query (ch[k][dig], x, dep - 1);
		return Query (ch[k][dig ^ 1], x, dep - 1) + (1ll << dep);
	}
	ll dfs(int k, int dep) {
		if(dep == -1) return 0;
		if(ch[k][0] && ch[k][1]) {
			ll ans = 1ll << 30;
			for (int i = l[ch[k][0]]; i <= r[ch[k][0]]; i++) {
				ans = min(ans, Query(ch[k][1], a[i], dep - 1) + (1ll << dep));
			}
			return dfs(ch[k][0], dep - 1) + dfs(ch[k][1], dep - 1) + ans;
		}
		else if(ch[k][0]) return dfs(ch[k][0], dep - 1);
		else if(ch[k][1]) return dfs(ch[k][1], dep - 1);
		return 0;
	}


	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) a[i] = Read();
		sort (a + 1, a + 1 + n);
		for (int i = 1; i <= n; i++) Insert (root, i, 30);
		printf ("%lld\n", dfs(root, 30));
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}