【CF888G】Xor-MST（01Trie，最小生成树）

看到异或最值要么是线性基要么是 01Trie。

线性基显然可以排除。

那么先把所有的 \(a_i\) 插入 01Trie 内。

然后发现对于任意两个数 \(a_i\) 和 \(a_j\)：

你发现它们在 \(rt \sim lca\) 路径上异或出来都是 \(0\)。

不妨定义两个结束节点的 “分离节点” 为它们的 \(lca\)，那么 \(a_i \operatorname{xor} a_j\) 的前 \(dep_{lca}\) 位都是 \(0\)。

对于任意两个结束节点，我们找到它们的 “分离节点” 并标记，不难发现标记点一共有 \(n-1\) 个（具体证明可以类似地参考虚树点数的证明）。

然后发现，对于任意一个标记点 ，要想让它左右子树内的结束节点联通，最优的方法就是在左右子树内各只找一个节点，然后把它们连起来。

所以 MST 中的每一条边和每一个标记点一一对应。

至于对于一个标记点找哪条边最优，可以用启发式合并，也就是枚举小的子树内的每一个结束节点，然后在大的子树内找到和它异或起来最大的。

对于每一个标记点都找一遍。

时间复杂度 \(O(n\log ^2 n)\)。

#include<bits/stdc++.h>

#define N 200010
#define ll long long
#define INF 0x7fffffff

using namespace std;

const int B=29;

int n,poww[35],a[N];
int ch[30*N][2],size[30*N],L[30*N],R[30*N];
int node;

void insert(int x,int id)
{
	int u=0;
	for(int i=B;i>=0;i--)
	{
		bool v=(x>>i)&1;
		if(!ch[u][v]) ch[u][v]=++node;
		u=ch[u][v];
		size[u]++;
		if(!L[u]) L[u]=id;
		R[u]=id;
	}
}

int query(int u,int x,int bit)
{
	if(bit<0) return 0;
	bool v=(x>>bit)&1;
	if(ch[u][v]) return query(ch[u][v],x,bit-1);
	else return query(ch[u][v^1],x,bit-1)+poww[bit];
}

ll dfs(int u,int bit)
{
	if(ch[u][0]&&ch[u][1])
	{
		bool v=(size[ch[u][1]]<size[ch[u][0]]);
		int ans=INF;
		for(int i=L[ch[u][v]];i<=R[ch[u][v]];i++)
			ans=min(ans,query(ch[u][v^1],a[i],bit-1)+poww[bit]);
		return dfs(ch[u][0],bit-1)+dfs(ch[u][1],bit-1)+ans;
	}
	if(ch[u][0]) return dfs(ch[u][0],bit-1);
	if(ch[u][1]) return dfs(ch[u][1],bit-1);
	return 0;
}

int main()
{
	poww[0]=1;
	for(int i=1;i<=B;i++)
		poww[i]=poww[i-1]<<1;
	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++)
		insert(a[i],i);
	printf("%lld\n",dfs(0,B));
	return 0;
}