题解：CF888G Xor-MST
题目大意：给定 \(n\) 个点的点权, 任意两点间边权是点权的异或和。求这张完全图的 MST 的权值。
思路：
Boruvka + Trie树 + 按位贪心。
关键就在于如何求出 Boruvka 中的 best 数组。
考虑对点权建 trie 树，对于节点 \(i\) 本轮的连边，就是找 “和它最相似” 的那个。
我最初的想法是只建一棵 trie 树，那么上述过程只需要每次 尽量 按照 \(a[i]\) 来走就行，但接着就发现不太对，因为求不出 "除去 \(i\) 所在集合中的点权 的影响后的最好方案"。
参考了这篇博客 ，发现给 全局 和 每个集合 分别建树是个很妙的想法，这样就可以轻松减去本集合的权值。具体实现是记录一个 siz 数组。
建树，统计答案都已经实现了，最后合并一下两棵树的信息就行。
感觉难点就在于理清楚思路。比较难写的是merge和query，细节比较多。
时间复杂度 \(O(30nlogn)\)
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=r;++i)
#define G(i,r,l) for(int i(r);i>=l;--i)
#define pii pair<int, int>
#define fi first
#define se second
using ll = long long;
using namespace std;
const int N = 2e5 +5;
const ll inf = 0x3f3f3f3f;
int a[N], fa[N], best[N], ch[50 * N][2], val[N], root[N], siz[50 * N], tail[50 * N];
int n, num = 0;
inline int get(int x){
return (fa[x]==x) ? x : fa[x] = get(fa[x]);
}
void insert(int &uu, int idx, int w){
if(!uu) uu = ++num;
int u = uu;
G(i, 30, 0){
int o = w >> i & 1;
siz[u] ++ ;
if(!ch[u][o]) ch[u][o] = ++num;
u = ch[u][o];
}
tail[u] = idx; siz[u] = 1;
}
void merge(int &p, int q){
if(!p || !q) return (void)(p = p + q);
merge(ch[p][0], ch[q][0]);
merge(ch[p][1], ch[q][1]);
siz[p] = siz[ch[p][0]] + siz[ch[p][1]];// 合并的一部分, 合并后q就不会再使用了, 所以只操作p就可以了
tail[p] = tail[q];//可以去掉这个赋值? 对于非叶子结点, tail都是0, 但对于叶子结点不清楚 >>>>>>>>>>>>>>>>>>>>>>>>>>
}
pii query(int u, int v, int w){
int ans = 0;
G(i, 30, 0){
int c = (w >> i) & 1;
if(ch[u][c] && siz[ch[u][c]] - siz[ch[v][c]] > 0) u = ch[u][c], v = ch[v][c];
else ans |= (1 << i), u = ch[u][c ^ 1], v = ch[v][c ^ 1];//v 的 移动本质上是 u 的同步, 所以都要 c ^ 1
}
return make_pair(tail[u], ans);//最后选中了哪个点, 代价是多少
}
ll boruvka(){
F(i, 1, n) fa[i] = i;
int pd = 1;
ll sum = 0;
while(pd){
pd = 0;
F(i, 1, n) val[i] = inf, best[i] = 0;
F(i, 1, n){
int x = get(i);
pii ret = query(root[0], root[x], a[i]);//找和a[i]异或得到的结果最小的点
int y = get(ret.fi), w = ret.se;
//注意y要找祖先!
if(x != y){//不在同一集合才能连
if(w < val[x]) best[x] = y, val[x] = w;
if(w < val[y]) best[y] = x, val[y] = w;
}
}
F(i, 1, n){
if(val[i] < inf && get(i) != get(best[i])){
//不用判 best[i]!=0, 因为如果=0, 那val[i]必然=inf, 这也是为什么best可以不清空的原因
sum += val[i];
pd = 1;
merge(root[get(i)], root[get(best[i])]);
fa[get(best[i])] = get(i);
}
}
}
return sum;
}
signed main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n; F(i, 1, n) cin >> a[i];
sort(a + 1, a + 1 + n);
n = unique(a + 1, a + 1 + n) - a - 1;//要去重, 相同权值的点连边其实可以全部等效在一个点上, 而且不去重算出来的siz会加倍, 问题就多了
F(i, 1, n)insert(root[0], i, a[i]), insert(root[i], i, a[i]);
cout << boruvka() << '\n';
return 0;
}