CF888G 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}$。

看到异或最小，想到 01 trie。

不妨先把所有数插入 01 trie，然后问题就变成不断选 lca 来合并这些点。不难发现 lca 深度越大越好，所以可以跑一遍 dfs，遍历到 $u$ 的时候：

• 若 $u$ 没有儿子，回溯；
• 若 $u$ 只有一个儿子，往唯一的儿子递归；
• 若 $u$ 有两个儿子，通过遍历左子树内所有的数来求合并两个子树的最小代价，给答案加上这个代价，再往两个儿子递归；

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=5000005,BS=30;

int n,a[S];
int cnt=1,son[S][2];
int lb[S],rb[S];
long long ans;

void dfs1(int u)
{
	if(lb[u]==0&&rb[u]==0) lb[u]=1e8,rb[u]=0;
	if(son[u][0]!=0)
	{
		int v=son[u][0];
		dfs1(v);
		lb[u]=min(lb[u],lb[v]),rb[u]=max(rb[u],rb[v]);
	}
	if(son[u][1]!=0)
	{
		int v=son[u][1];
		dfs1(v);
		lb[u]=min(lb[u],lb[v]),rb[u]=max(rb[u],rb[v]);
	}
}

inline int que(int val,int rt,int bse)
{
	int u=rt,res=0;
	for(int i=bse;i>=0;i--)
	{
		int id=val>>i&1;
		if(son[u][id]==0) u=son[u][id^1],res+=1<<i;
		else u=son[u][id];
	}
	return res;
}

void dfs2(int u,int bse)
{
	if(son[u][0]!=0) dfs2(son[u][0],bse-1);
	if(son[u][1]!=0) dfs2(son[u][1],bse-1);
	if(son[u][0]!=0&&son[u][1]!=0)
	{
		int mn=que(a[lb[son[u][0]]],son[u][1],bse-1);
		for(int i=lb[son[u][0]]+1;i<=rb[son[u][0]];i++) mn=min(mn,que(a[i],son[u][1],bse-1));
		ans+=(long long)mn+(1<<bse);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		int u=1;
		for(int j=BS;j>=0;j--)
		{
			int id=a[i]>>j&1;
			if(son[u][id]==0) son[u][id]=++cnt;
			u=son[u][id];
		}
		lb[u]=rb[u]=i;
	}
	dfs1(1);
	dfs2(1,BS);
	printf("%lld\n",ans);
	return 0;
}