[ Xor最小生成樹 分治 字典樹 ] Codeforces888G Xor-MST

裸的 xor x o r 最小生成樹。

枚舉每一位，把這一位為 0 0 的放在一起形成一個連通塊，為 11 的放在一起形成一個連通塊，之間用字典樹求一條最小邊，然後分治做。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=;
int k,n,m;
vector<int> g;
int Rt,nx[M][],num;
void Insert(int& x,int y,int d) {
    if(!x) x=++num,nx[x][]=nx[x][]=;
    if(d==-) return;
    Insert(nx[x][y>>d&],y,d-);
}
int Query(int x,int y,int d) {
    if(d==-) return ;
    int p=y>>d&;
    if(nx[x][p]) return Query(nx[x][p],y,d-);
    return Query(nx[x][p^],y,d-)+(<<d);
}
ll Solve(vector<int>g,int d) {
    if(!g.size()||d==-) return ;
    vector<int> a[];
    for(int v:g) a[v>>d&].push_back(v);
    ll Ans=Solve(a[],d-)+Solve(a[],d-);
    if(a[].size()&&a[].size()) {
        Rt=num=;
        for(int v:a[]) Insert(Rt,v,d-);
        int Res=<<d;
        for(int v:a[]) Res=min(Res,Query(Rt,v,d-));
        Ans+=Res+(<<d);
    }
    return Ans;
}
int main() {
    scanf("%d",&n);
    for(int i=;i<=n;i++) {
        int x;scanf("%d",&x);
        g.push_back(x);
    }
    printf("%I64d\n",Solve(g,));
    return ;
}