最小异或生成树

例题: Codeforces 888G

给定 $n$ 个结点的无向完全图。每个点有一个点权为 $a_{i}$ 。连接 $i$ 号结点和 $j$ 号结点的边的边权为 $a_{i} \oplus a_{j}$

求这个图的 MST 的权值。

$1 \leq n \leq 2 \times 10^{5}, 0 \leq a_{i}<2^{30}$

题解

考虑将$n$个点权插入$0-1Trie$树中，问题转化为将$Trie$树的叶子连接起来。

若两个叶子$u,v$要建边，那么只需要从$lca(u,v)$开始计算异或即可。因此，若$lca(u,v)$的深度越大，则$e(u,v)$的权值越小。

假设$p$为$Trie$树上的非叶子节点，且$p$有两个子节点。（可以证明，这样的点$p$总共有$n-1$个。）

当dfs到点$p$时，先让左/右子树内对应的的所有叶子联通，接着联通左右两棵子树即可。

思路近似于boruvka（一种分治求MST的算法）。

AC代码

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 100;

int trie[maxn * 33][2], l[maxn * 33], r[maxn * 33], node_cnt = 1;
int a[maxn], n;

void build(int rt, int val, int dep, int tag){
    if(l[rt] == 0) l[rt] = tag;
    r[rt] = max(r[rt], tag);

    if(dep > 30) return;
    
    int bit = (val & (1<<(30-dep))) > 0;
    if(trie[rt][bit] == 0) trie[rt][bit] = ++node_cnt;
    build(trie[rt][bit], val, dep + 1, tag);
}

int query(int rt, int val, int dep){
    if(dep > 30) {
        return 0;
    }
    int bit = (val & (1<<(30-dep))) > 0;
    if(trie[rt][bit] == 0){
        return query(trie[rt][bit ^ 1], val, dep + 1) + (1 << (30-dep));
    }
    return query(trie[rt][bit], val, dep + 1);
}

ll dfs(int rt, int dep){
    if(dep > 30) return 0;
    if(trie[rt][0] && trie[rt][1]){
        ll mn = INT_MAX;
        for(int i=l[trie[rt][0]]; i<=r[trie[rt][0]]; i++){
            mn = min(mn, query(trie[rt][1], a[i], dep + 1) + (1ll << (30 - dep)));
        }
        return dfs(trie[rt][0], dep + 1) + dfs(trie[rt][1], dep + 1) + mn;
    }
    if(trie[rt][0]) return dfs(trie[rt][0], dep + 1);
    return dfs(trie[rt][1], dep + 1);
}

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    for(int i=1; i<=n; i++)
        build(1, a[i], 0, i);
    cout << dfs(1, 0) << '\n';
}
  
signed main(){
    Android;
    solve();
}

例题: 2020牛客暑期多校训练赛5-B

显然，只要操作符合题目要求，则$\forall u,v(u\ne v),path(u,v)=C$，其中$C$为某一常数（不因加边/删边而改变），$path(u,v)$代表路径上的边权异或和。

那么，可以给每个点设置一个点权$w$，两个点之间的边权为两点权的异或。

问题转化为最小异或生成树的求解。

// 省略
const int maxn = 1e5 + 100;

int trie[maxn * 33][2], l[maxn * 33], r[maxn * 33], node_cnt = 1;
int a[maxn], n;
vector<pii> G[maxn];

void build(int rt, int val, int dep, int tag)// 省略
int query(int rt, int val, int dep)// 省略
ll dfs(int rt, int dep)// 省略

void build_a_array(int rt, int fa, int cur){
    a[rt] = cur;
    for(pii ve:G[rt]){
        int dest = ve.first;
        if(dest == fa) continue;
        build_a_array(dest, rt, cur ^ ve.second);
    }
}

void solve(){
    cin >> n;
    
    for(int i=1, u, v, w; i<n; i++){
        cin >> u >> v >> w;
        u++, v++;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    build_a_array(1, 0, 0);

    sort(a + 1, a + 1 + n);
    for(int i=1; i<=n; i++)
        build(1, a[i], 0, i);
    cout << dfs(1, 0) << '\n';
}
  
signed main(){
    Android;
    solve();
}