挺简单的知识点（？）
概念
首先 Kruskal 算法是用来求最小生成树的算法之一，其思想是贪心。
而 Kruskal 重构树就是将整张图重建为二叉树。
在跑 Kruskal 的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。
首先新建 \(n\) 个集合，每个集合恰有一个节点，点权为 \(0\) 。
每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将两个集合的根节点分别设为新建点的左儿子和右儿子。然后我们将两个集合和新建点合并成一个集合。将新建点设为根。
不难发现，在进行 \(n-1\) 轮之后我们得到了一棵恰有 \(n\) 个叶子的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 Kruskal 重构树。
比如这张图
它会被重构成
性质
Kruskal 重构树有很多性质
-
Kruskal 重构树是一棵二叉树
-
原图中所有节点与 Kruskal 重构树上的叶子节点一一对应
-
每个节点的点权是其子树所有节点（包括本身）中的最大点权（不考虑叶子结点）
-
两点之间所有简单路径上最大边权的最小值 \(=\) 最小生成树上两个点之间的简单路径上的最大值 \(=\) Kruskal 重构树上两点之间的LCA的权值。
Code
动态数组版
const int N=1e5;
int n,m;
int k,t,s,d;
struct node
{
int u,v,w;
bool operator<(const node& e) const {return w<e.w;}
}ee[N];
vector<int> e[N];
int d[N],f[N],a[N],down[N],fa[N][18];
int cnt;
int find(int x)
{
return f[x]==x ? f[x] : f[x]=find(f[x]);
}
int Kruskal()
{
sort(ee+1,ee+1+m);
for(int i=1;i<=2*n;++i)
f[i]=i;
cnt=n;
for(int i=1;i<=m;++i)
{
int u=find(ee[i].u),v=find(ee[i].v);
if(u!=v)
{
d[++cnt]=ee[i].w;
f[u]=f[v]=f[cnt]=cnt;
e[cnt].fush_back(u);
e[cnt].fush_back(v);
}
}
return cnt;
}
例题
在写
参考资料
标签：重构,int,Kruskal,笔记,点权,集合,节点 From： https://www.cnblogs.com/HSxh/p/17922250.html