Kruskal重构树

blog：acm-Kruskal重构树学习笔记

简单来讲，就是在Kruskal算法进行的过程中，我们把最小生成树的边权改为点权。这样，原树的节点个数变成2n-1个，并且有着许多有趣的性质。

性质

• 每个节点的点权是其子树所有节点(包括本身)中的最大点权(不考虑叶子节点)
• 原树上任意两个节点之间路径上最大边权的最小值(最小瓶颈路)是它们在Kruskal重构树上最近公共祖先(lca)的点权
• Kruskal重构树是一颗二叉树
• 原图中的所有节点与Kruskal重构树上的叶子节点一一对应

代码

void Ex_Kruskal() { // Kruskal重构树
    int idx=n, lim=n<<1;  // 2n-1个点，当前已经有idx(n)个节点
  	sort(edge+1,edge+1+m);
    for(int i=1;i<=lim;++i) fa[i]=i;
    for(int i=1;i<=m;++i) {
        int fx=getFather(edge[i].from), fy=getFather(edge[i].to); // 并查集
        if(fx!=fy) { // 不成环
            fa[fx]=fa[fy]=++idx; // 开新节点
            val[idx]=edge[i].w;
            add(idx,fx), add(idx,fy);
            if(idx==lim-1) break; // 到达了上限
        }
    } 
  	return;
}

一道有意思的CF题：Click here