Trie

0-1 Trie

常见应用: 异或类问题

CF888G

题目要求用两个权值相互异或得出的边求最小生成树，一共\(\frac{n(n-1)}{2}\)条边。

如果我们对于\(n\)个权值建出\(0-1 Trie \(树，我们会发现\)u,v\)的异或值就是从\(lca_{u,v}\)分别到\(u,v\)所表示的数的异或值(因为\(lca\)之前异或没了)，那么我们所求的恰好转化为求出所有可能的\(lca\)。

看图会发现，如果点权值互不相同，那么这样的\(lca\)恰有\(n-1\)个，满足生成树的条件。如果有相同的情况，那么相当于多出了几条边权为\(0\)的边，由于一定要选，故不影响最终答案。

所以，我们直接在\(Trie\)树上\(dfs\),如果碰到有两个子节点的\(lca\),就搜索一遍子树，得出答案。(搜索函数作用是在两个不同子树中分别找出一个叶子节点，使其异或和最小)

而搜索函数\(find\)中，要分情况讨论。

1. 当前深度无贡献

即从当前节点到两个子节点的边相同，那么答案就是两个子树的答案取\(\min\).

1. 当前深度有贡献

即两条边不同，那么答案是两子树答案取\(\min\)加上\(2^{dep}\).

如果没有满足条件的两条边，就返回\(INF\).

如果两种情况下两个子树都是\(INF\),就说明两个子树已经是叶子节点，则返回\(0\).

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int N=2e5+10,DEP=30,M=N*DEP,INF=1e18;
int n,m,tot,rt,ans;
int a[N];
int T[M][2];
bool cmp(int a,int b){
    return a<b;
}
void Insert(int now,int x){
    for(int i=DEP;i>=0;--i){
        int id=(x>>i)&1;
        if(!T[now][id]) T[now][id]=++tot;
        now=T[now][id];
    }
}
int Find(int r1,int r2,int dep){
    if(dep<0) return 0;
    int a1=INF,a2=INF,a=-1;
    if(T[r1][0] && T[r2][0]) a1=Find(T[r1][0],T[r2][0],dep-1);
    if(T[r1][1] && T[r2][1]) a2=Find(T[r1][1],T[r2][1],dep-1);
    a=min(a1,a2);
    if(a!=INF) return a;
    a1=INF,a2=INF,a=-1;
    if(T[r1][0] && T[r2][1]) a1=Find(T[r1][0],T[r2][1],dep-1)+(1ll<<dep);
    if(T[r1][1] && T[r2][0]) a2=Find(T[r1][1],T[r2][0],dep-1)+(1ll<<dep);
    a=min(a1,a2);
    if(a!=INF) return a;
    return 0;
}
void dfs(int x,int dep){
    if(dep<0) return;
    if(T[x][0] && T[x][1]) ans+=Find(T[x][0],T[x][1],dep-1)+(1ll<<dep);
    if(T[x][0]) dfs(T[x][0],dep-1);
    if(T[x][1]) dfs(T[x][1],dep-1);
}
signed main(){
    scanf("%lld",&n);rt=tot=ans=0;
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),Insert(rt,a[i]);
    dfs(rt,DEP);
    printf("%lld",ans);
    return 0;
}