做法：Borůvka+01字典树

思路：

  • dfs走法：有左儿子就走左儿子，有右儿子就走右儿子，同时存在则合并取min后加上深度的值

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=200010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;

int a[N];

struct Trie {
    int nex[N*32][2],cnt=0,now=0;
     int l[N*32],r[N*32];
     void init(){
         mst(l,INF);
    }
    void insert(int x,int id) { 
        int p = 0;//下标 
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if (!nex[p][c]) nex[p][c] = ++cnt; 
            p = nex[p][c];
            l[p]=min(l[p],id),r[p]=max(r[p],id);//确定当前节点所对应的区间
        }
    }
    int query(int p,int x,int dep){
        if(dep<0) return 0;
        int c = x>>dep&1;
        if(nex[p][c]) return query(nex[p][c],x,dep-1);
        else return query(nex[p][c^1],x,dep-1)+(1<<dep);
    }
    ll dfs(int p,int dep){
         if(dep<0) return 0;
         if(nex[p][0]&&nex[p][1]){ //合并 
             int minn=INF;
             for(int i=l[nex[p][0]];i<=r[nex[p][0]];i++) minn=min(minn,query(nex[p][1],a[i],dep-1));
             return dfs(nex[p][0],dep-1)+dfs(nex[p][1],dep-1)+(1<<dep)+minn;
        }
        if(nex[p][0]) return dfs(nex[p][0],dep-1);
        if(nex[p][1]) return dfs(nex[p][1],dep-1);
        return 0;
    }
} t;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
    int n;cin>>n;
    t.init();
    rep(i,1,n) cin>>a[i];
    sort(a+1,a+1+n);
    rep(i,1,n) t.insert(a[i],i);
    cout<<t.dfs(0,30)<<"\n";
    return 0;
}