题面
给定一个\(n\)个节点的完全图，每个节点有个编号\(a_i\),节点\(i\)和节点\(j\)之间边的权值为\(a_i\bigoplus a_j\),求该图的最小生成树的权值和。
\(n\leq2*10^5\)
解析
有个新奇的最小生成树算法：
\(Boruvka\)算法： 先对于每个点，选择在所有与之相连的边中，权值最小的边，并将这条边加入到最小生成树中。 显然这样连出来的边会形成一个森林，并且连边后连通块个数至少减半。 然后我们将每个连通块再看成一个点，重复以上算法即可。 时间复杂度\(O(mlogn)\)。
从高位往低位贪心。
把所有点按当前位为\(0\)还是\(1\)分为两类。 显然这两类内部会形成联通块。然后这两类间一定会有连边。
根据上面那个算法，如果我们选出两类数之间边权最小的那条边,这条边一定在最小生成树中。 因为这是当前状态下（两个大连通块）运行\(B\)算法后将得到的结果。 接下来分治对两类数内部进行处理。找边权最小值，直接\(Trie\)树即可。
总复杂度\(O(mlogn)\)。
#include#include #include #include #include #include #include #define re register#define il inline#define ll long long#define pb push_back#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int mod=1e9+7,N=2e5+100;int n,tot,rt,t[N<<5][2];il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il void Insert(re int &u,re int x,re int d){ if(!u) u=++tot,t[u][0]=t[u][1]=0; if(d<0) return; Insert(t[u][(x>>d)&1],x,d-1);}il int Query(re int u,re int x,re int d){ if(d<0) return 0;re int c=(x>>d)&1; if(t[u][c]) return Query(t[u][c],x,d-1); if(t[u][c^1]) return Query(t[u][c^1],x,d-1)^(1<