Description
给你一张完全图，每一个点有一个点权为 \(a[i]\)，边 \((u,v)\) 的边权为 \(a[u]\) \(xor\) \(a[v]\)，求最小生成树的边权和.
solution
正解：trie树＋贪心
考虑优化ｋｒｕｓｋａｌ的过程，我们找出边权最小的且边的两边没有连通的边，选择连接，方法是在ｔｒｉｅ树上贪心，首先我们对所有的点建立ｔｒｉｅ树，然后考虑怎么样连边最优，容易发现，一定是选择二进制下交最多的两个点，那么一定对应ｔｒｉｅ树上的一个前缀，所以我们只需要ｄｆｓ ｔｒｉｅ树，自底向上合并即可，考虑枚举左右子树中ｓｉｚｅ小的，在另一棵子树上遍历求得异或最小值，启发式合并的复杂度是 \(O(n*logn)\) 的，加上ｔｒｉｅ树的操作，总复杂度为 \(O(n*log2n)\)
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=4000005;
inline int gi(){RG int str=0;RG char ch=getchar();while(ch>'9' || ch<'0')ch=getchar();while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();return str;
}
int n,rt=0,bin[30],sz[N],ls[N],rs[N],totnode=0;
ll ans=0;il void ins(int &x,int v,int d){if(!x)x=++totnode;if(d==-1){sz[x]=1;return ;}if(bin[d]&v)ins(rs[x],v,d-1);else ins(ls[x],v,d-1);sz[x]=sz[ls[x]]+sz[rs[x]];
}il int qry(int x,int v,int d){if(d==-1)return 0;if(v&bin[d]){if(rs[x])return qry(rs[x],v,d-1);return qry(ls[x],v,d-1)+bin[d];}else{if(ls[x])return qry(ls[x],v,d-1);return qry(rs[x],v,d-1)+bin[d];}
}il int merge(int x,int y,int d,int val,int sd){if(d==-1)return qry(y,val,sd);int ret=1<<30;if(ls[x])ret=min(ret,merge(ls[x],y,d-1,val,sd));if(rs[x])ret=min(ret,merge(rs[x],y,d-1,val+bin[d],sd));return ret;
}il void dfs(int x,int d){if(d==-1)return ;if(ls[x])dfs(ls[x],d-1);if(rs[x])dfs(rs[x],d-1);if(!ls[x] || !rs[x])return ;int l=ls[x],r=rs[x];if(sz[l]>sz[r])swap(l,r);ans+=merge(l,r,d-1,0,d-1)+bin[d];
}void work()
{scanf("%d",&n);for(int i=1;i<=n;i++)ins(rt,gi(),29);dfs(rt,29);cout<<ans<<endl;
}int main()
{bin[0]=1;for(int i=1;i<=29;i++)bin[i]=bin[i-1]<<1;work();return 0;
}