D 算法模板（Boruvka's Algorithm）

Description

为了方便你测试，本题为D题简化版。

You are given a complete undirected graph with

Calculate the weight of the minimum spanning tree in this graph.

Input

The first line contains

The second line contains

Output

Print one number — the weight of the minimum spanning tree in the graph.

Examples

Sample 1 Input

1
1

Sample 1 Output

Sample 2 Input

4
0 7 2 4

Sample 2 Output

Sample 3 Input

13
1 1 4 5 1 4 1 9 1 9 8 1 0

Sample 3 Output

这个是模板啦
相信大家肯定都被这种奇奇怪怪的完全图上搞事情的题目恶心过吧
我当初就遇到一个完全图里面边权是点权的gcd，然后求最短路的题目。
那个好像是一个线段树优化建图吧

这个是xor的边权。
xor，自然是想到了trie树啦
trie树能够非常自然的求出每一个点和其他点之间最小的边.
最小生成树有一个贪心，如果有一条目前最小的边，而且是连接了两个目前不连通的联通块，那么，选择它就是最优的。
我们先给每一个数排一个序。
在trie树中，我们把每一个数转化为二进制存放进去，然后对于每一个子树，我们记录它里面节点的下标的最大值和下标的最小值
这样我们就知道了这里面有什么数字了。
然后我们就枚举左子树里面的节点尝试和右子树里面的节点进行匹配

对于一个子树内的点，我们把他们先连起来，这样肯定不会不优的
然后就没啥了

//加油
#include<bits/stdc++.h>
#define ll long long
#define lc trie[x][0]
#define rc trie[x][1]
using namespace std;
ll a[5000001],L[5000001],R[5000001],trie[5000001][2],cnt,n;
inline ll read()
{
    char c=getchar();ll a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;
    return a*b;
}
void insert(ll &p,ll x,ll i)
{
    if(p==0)p=++cnt;
    L[p]=min(L[p],x);
    R[p]=max(R[p],x);//记录这个区间所对应的下标 
    if(i<0)return;
    ll val=(a[x]>>i)&1;
    insert(trie[p][val],x,i-1);
}
ll ask(ll p,ll x,ll i)
{
    if(i<0)return 0;
    ll val=(x>>i)&1;
    if(trie[p][val])return ask(trie[p][val],x,i-1);
    return ask(trie[p][val^1],x,i-1)+(1<<i);
}
ll dfs(ll x,ll dep)
{
    if(dep<0)return 0;
    if(R[lc]&&R[rc])//判断是否有这个子树 
    {
        ll res=1e9;
        for(ll i=L[lc];i<=R[lc];i++)//枚举左子树的端点，去右子树匹配 因为是拍过序了，所以解决的数都会非常的靠近，只需要记录一下下标就好了 
        {
            res=min(res,ask(rc,a[i],dep-1));
        }
        return dfs(lc,dep-1)+dfs(rc,dep-1)+res+(1<<dep);
    }
    if(R[lc])return dfs(lc,dep-1);
    if(R[rc])return dfs(rc,dep-1);
    return 0;
}
int main()
{
    freopen("qingyuqaq.in","r",stdin);
    freopen("qingyuqaq.out","w",stdout);
    n=read();
    for(ll i=1;i<=n;i++)
    {
        a[i]=read();
    }
    sort(a+1,a+1+n);
    memset(L,30,sizeof(L));
    ll root=0;
    for(ll i=1;i<=n;i++)insert(root,i,30);
    cout<<dfs(root,30)<<endl;
    return 0;
}