Boruvka 最小生成树

思想及流程

Boruvka 是 Kruskal 和 Prim 两者的结合算法，“博采众长”因此能轻松解决一类两者很难快速解决的问题，尤其是完全图（稠密图）的 MST。

Boruvka 的思想是：最开始每个点都是一个孤立的连通块，之后经过多轮的迭代，向 MST 边集中加边，把边的两端的连通块合并。加边的方法是：对每个连通块找到离它最近的连通块，这条边叫做这个连通块的“最小边”，每一轮结束时将所有拥有最小边的连通块的最小边加入 MST 边集；这一步可以用 \(O(E)\) 地枚举边并更新两端连通块的最小边来做到，但很多时候也会采用 dp 等方法直接求得这个离它最近的连通块。每一轮结束后，所有连通块都设为“没有最小边”，并进入下一轮。对于一个连通图来说，合并一轮下来，都会将连通块的数量至少减半，极端情况是 \(V/2\) 个连通块和另外 \(V/2\) 个连通块刚好分别是 \(V/2\) 个最小边的两端。这样一来，最多只会迭代 \(\log V\) 轮，常见时间复杂度为 \(O(E\log V)\)。（当然主要取决于找最小边的方法）

推荐题目

CODE-FESTIVAL-2017-FINAL Tree MST

这个题就是典型的使用了 dp 的方法来寻找连通块的最近连通块。在每轮中，我们可以用树形 dp 维护一个点的子树里离它最近的两个颜色互异的点（最近的含义是“完全图”中边权最小）。这样一来，这两个点中至少一个的颜色和 \(x\) 不一样，而这样的信息也容易为父亲所用。再进行一道换根 dp，得到离每个点最近的、跟这个点颜色不一样的点，用“点的最小边”更新点所在连通块的最小边，照搬 Boruvka 的流程即可。

/*
Todo list:
1. How to embed 'whether a node has miniedge' into ppp
2. How to connect in BCJ
3. You haven't changed vertex to color! DONE
*/
#include 
#define int long long
#define pii pair
#define ppp pair
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int N=2e5+5,INF=1e17;
const ppp nu=mkp(mkp(INF,0),mkp(INF,0));
int n,n_v,n_e,ans,w[N],fa[N];
bool bk[N];
vectorgr[N],G[N];
vectorf[N]; // nearest 2 colors in x's subtree
pairmn[N]; // to store the miniedges for each routine
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unite(int x,int y){fa[find(y)]=find(x);}
inline void adde(int u,int v,int w){
	gr[u].push_back(mkp(v,w)),gr[v].push_back(mkp(u,w));
}
void dfs0(int x,int p){
	for(int i=0;igm(paira,pairb){
	return a.setmp;
	tmp.push_back(a.fi),tmp.push_back(a.se),tmp.push_back(b.fi),tmp.push_back(b.se);
	sort(tmp.begin(),tmp.end(),[](pii a,pii b){return a.fipre,suf;
	f[x].resize(G[x].size()+1),pre.resize(G[x].size()),suf.resize(G[x].size());
	for(int i=0;i'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
signed main(){
//	freopen("input.in","r",stdin);freopen("output.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)w[i]=read(),fa[i]=i;
	for(int i=1,u,v,_w;i1;i++)Boruvka();
	cout<