大概就是：初始每個點都是獨立的集合，每次merge過程從所有獨立集合出發，找到一條權值最小(權值相同則編号)最小的連向其它集合的邊，然後合并集合。顯然每次都會使得集合數減少一半，是以合并次數是log級别的。
例題：
luogu3366mst模闆題
直接模拟算法過程即可。。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int n,m;
int s[N],t[N],w[N];
struct Boruvka{
int f[N],use[N],best[N];
void init(){
for(int i=1;i<=n;i++)f[i]=i,best[i]=0;
for(int i=1;i<=m;i++)use[i]=0;
}
int find(int x){
return f[x]==x?x:(f[x]=find(f[x]));
}
int better(int x,int y){
if(!y)return 1;
if(w[x]<w[y])return 1;
return x<y;
}
LL get(){
int merge=0;
LL sum=0;
while(merge!=n-1){
for(int i=1;i<=m;i++){
if(use[i])continue;
int x=find(s[i]),y=find(t[i]);
if(x==y)continue;
if(better(i,best[x]))best[x]=i;
if(better(i,best[y]))best[y]=i;
}
for(int i=1;i<=n;i++){
if(best[i]){
int x=find(s[best[i]]),y=find(t[best[i]]);
if(x!=y){
use[best[i]]=1;
f[x]=y;
merge++;
sum+=w[best[i]];
}
best[i]=0;
}
}
}
return sum;
}
}g;
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>s[i]>>t[i]>>w[i];
g.init();
cout<<g.get()<<'\n';
return 0;
}
cf888G
把所有值建一個01字典樹，然後我們貪心的考慮生成樹的過程，因為跟二進制有關系，是以從大到小貪心是合法的。我們從字典樹的一個節點考慮，節點的左右兒子必然不同為一個集合。而一個兒子節點代表的集合連出去的最小權值邊，必然是跟另一個兒子節點連才是最優的（二進制異或的性質）。那每次遞歸處理左右兒子，然後再合并左右兒子代表的集合就可以了。合并左右兒子的時候運用啟發式合并的思想，枚舉size小的一邊，在另一個兒子節點代表子樹上查異或最小的值。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 6e6 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int n,a[N];
vector<int>v[N];
struct trie{
int cnt,t[N][2],ta[N];
void insert(int z,int x,int y){
v[z].pb(y);
if(x<0){
return ;
}
bool st=1<<x&y;
if(!t[z][st])t[z][st]=++cnt;
insert(t[z][st],x-1,y);
}
int query(int z,int x,int y){
if(x<0)return 0;
bool st=1<<x&y;
if(t[z][st]) {
return query(t[z][st], x - 1, y);
} else {
return query(t[z][st ^ 1], x - 1, y) + (1 << x);
}
}
}g;
LL gao(int o,int q){
if(v[o].size()<=1)return 0;
LL ans=0;
for(int i=0;i<2;i++){
if(g.t[o][i]){
ans+=gao(g.t[o][i],q-1);
}
}
if(!g.t[o][0]||!g.t[o][1])return ans;
int x=g.t[o][0],y=g.t[o][1];
if(v[x].size()>v[y].size())swap(x,y);
LL cm=1e18;
for(auto k:v[x]){
cm=min(cm,1ll*g.query(y,q-1,k));
}
ans+=cm+(1<<q);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin>>n;g.cnt=1;
for(int i=1;i<=n;i++)cin>>a[i];
//字典樹上，兩個不同子樹必然屬于不同的聯通快，需要用一個最小權值的邊連一起，可以用啟發式合并的
//思想，用小的到大的裡面枚舉。。。
for(int i=1;i<=n;i++)g.insert(1,30,a[i]);
cout<<gao(1,30)<<'\n';
return 0;
}
//200000*30
2020牛客多校5B
因為題目要求每時每刻必須聯通，且環上異或為0，那麼任意兩點的連起來的邊權都是固定的。
(x,y)的邊權=(1-x)的值^(1-y)的值，把每個點z的值 都變成(1-z)路徑上邊權的異或和。
然後就跟上題一模一樣了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e6 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int n,a[N];
vector<int>v[N];
struct trie{
int cnt,t[N][2];
void insert(int z,int x,int y){
v[z].pb(y);
if(x<0){
return ;
}
bool st=1<<x&y;
if(!t[z][st])t[z][st]=++cnt;
insert(t[z][st],x-1,y);
}
int query(int z,int x,int y){
if(x<0)return 0;
bool st=1<<x&y;
if(t[z][st]) {
return query(t[z][st], x - 1, y);
} else {
return query(t[z][st ^ 1], x - 1, y) + (1 << x);
}
}
}g;
LL gao(int o,int q){
if(v[o].size()<=1)return 0;
LL ans=0;
for(int i=0;i<2;i++){
if(g.t[o][i]){
ans+=gao(g.t[o][i],q-1);
}
}
if(!g.t[o][0]||!g.t[o][1])return ans;
int x=g.t[o][0],y=g.t[o][1];
if(v[x].size()>v[y].size())swap(x,y);
LL cm=1e18;
for(auto k:v[x]){
cm=min(cm,1ll*g.query(y,q-1,k));
}
ans+=cm+(1<<q);
return ans;
}
const int M=1e5+1;
vector<pair<int,int>>G[N];
int vis[N];
void dfs(int x,int t=0,int pre=0){
a[x]=t;
for(auto k:G[x]){
if(k.fi!=pre){
dfs(k.fi,t^k.se,x);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin>>n;g.cnt=1;
for(int i=1;i<n;i++){
int s,t,w;
cin>>s>>t>>w;
++s;++t;
G[s].pb({t,w});
G[t].pb({s,w});
}
dfs(1);
for(int i=1;i<=n;i++)g.insert(1,30,a[i]);
cout<<gao(1,30)<<'\n';
return 0;
}
//200000*30