Xor-MST

咕了好久终于来写了

题意

给你个点的无向完全图，每个点有点权，每两个点之间的边权是点权的值。问最小生成树边权和。

思路

从别人那里学来的巧妙思路，我们考虑树，首先，我们先把样例从高位到低位插入线性基。容易发现，对于每个叶子节点，既每个点值之间，是需要互相连边，那么求他们以后的边的异或值即可。由此可得，若是的深度越深，便越优。因为我们是从高位到低位插入的，所以浅的点权值较大，要尽量避免选择浅的点。我们把可能是的点找出来，可以发现如果均不相等那么这样的点就恰好有个。如果有,我们建一条边连接，，权值为，对答案完全没有影响。
我们每找到这样的点，就暴力贪心下去：
每次尽量同时走左儿子或右儿子；
如果两个都有，就两个都走，然后取 。
如果两个只有不一样的儿子，就在返回值加上这一深度的值，然后继续走

代码

#include<bits/stdc++.h>
#define int long long
const int N=1e5+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n;
int son[2][N*30+10],tot,ans;

inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void Insert(int a)
{
    int now=0,id;
    for(int i=30;i>=0;i--)
    {
        id=(a>>i)&1;
        if(!son[id][now])son[id][now]=++tot;
        now=son[id][now];
    }
}

int find(int r1,int r2,int b)
{
    if(b<0) return 0;
    int a1=-1,a2=-1;
    if(son[0][r1]&&son[0][r2]) a1=find(son[0][r1],son[0][r2],b-1);
    if(son[1][r1]&&son[1][r2]) a2=find(son[1][r1],son[1][r2],b-1);
    if(~a1&&~a2) return min(a1,a2);
    if(~a1) return a1;
    if(~a2) return a2;
    if(son[1][r1]&&son[0][r2]) a1=find(son[1][r1],son[0][r2],b-1)+(1<<b);
    if(son[0][r1]&&son[1][r2]) a2=find(son[0][r1],son[1][r2],b-1)+(1<<b);
    if(~a1&&~a2) return min(a1,a2);
    if(~a1) return a1;
    if(~a2) return a2;
}

void dfs(int a,int b)
{
    if(b<0) return;
    if(son[0][a]&&son[1][a]) ans+=1ll*find(son[0][a],son[1][a],b-1)+(1ll<<b);
    if(son[0][a]) dfs(son[0][a],b-1);
    if(son[1][a]) dfs(son[1][a],b-1);
}

signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
        Insert(read());
    dfs(0,30);
    printf("%lld\n",ans);
    return 0;
}