CF888G Xor-MST

题意：
给你n个数，每个数有一个值。
问你这n个数的最小生成树为多少，两点之间的边权为异或值。

题解：
参考了洛谷上的一个题解，总觉得这样的时间复杂度会爆炸，但是确确实实没爆炸。
我们每次去合并两个点，要想尽量使全值小，对于一颗字典树来说，就要尽量先合并越靠树叶的结点，一个叶子结点对应一个结点。
那么我们对于一颗字典树来说，我们把他运用到最近公共祖先上，把所有最近公共祖先的结点来说，他有两个孩子，也就是要练的结点就是所有的最近公共祖先的结点。
对于每一个公共祖先结点，我们对其左右儿子尽心递归查找，尽量找到最小结点的值！

也就是说对于某个结点，他拥有左右节点，无法避免的是让答案加上这一深度的值，但是对于左孩子递归下去的分支，和右孩子递归下去的分支。要尽量相同（相同异或为0，使最小生成树尽量小）。

对于每一个递归，要遍历他的孩子，尽量让同一深度 两个数二进制第i尾不相同。

图片来自于 周道_Althen

每次尽量同时走左儿子或右儿子；
如果两个都有，就两个都走，然后返回值取 min 。

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =1e7+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int trie[maxn][2];
int cnt;

void ins(int x){
    int node=0;
    for(int i=30;i>=0;i--){
        int t=(x>>i)&1;
        if(!trie[node][t]) trie[node][t]=++cnt;
        node=trie[node][t];
    }
}

int ifind(int x,int y,int rem){
    if(rem<0) return 0;
    int a=-1,b=-1;
    if(trie[x][0]&&trie[y][0]) a=ifind(trie[x][0],trie[y][0],rem-1);
    if(trie[x][1]&&trie[y][1]) b=ifind(trie[x][1],trie[y][1],rem-1);
    if(~a&&~b) return min(a,b);
    if(~a) return a;
    if(~b) return b;
    if(trie[x][1]&&trie[y][0]) a=ifind(trie[x][1],trie[y][0],rem-1)+(1<<rem);
    if(trie[x][0]&&trie[y][1]) b=ifind(trie[x][0],trie[y][1],rem-1)+(1<<rem);
    if(~a&&~b) return min(a,b);
    if(~a) return a;
    if(~b) return b;

}
int ans=0;
void dfs(int x,int y){
    if(y<0) return ;
    if(trie[x][0]&&trie[x][1]) ans+=1ll*ifind(trie[x][0],trie[x][1],y-1)+(1ll<<y);
    if(trie[x][0]) dfs(trie[x][0],y-1);
    if(trie[x][1]) dfs(trie[x][1],y-1);

}
signed main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        ins(x);
    }
    dfs(0,30);
    cout<<ans<<endl;
    return 0;
}