Kruskal 重构树

一个比较冷门的算法。

Kruskal 重构树

在 $\tt{Kruskal}$ 的过程，并做这样一个操作：

• 从小到大遍历所有边，设当前边两端为 $x$，$y$；
• 判断 $x$ 、$y$ 是否在同一并查集；
• 若不在，新建一个点权为这条边边权的节点 $p$ ，将 $x$ 、$y$ 分别于 $p$ 连边，并把 $x$ 、$y$ 的并查集合并到 $p$ 上。

for (int i = 1; i <= n; i ++) {
	int p = getfa(e[i].x), q = getfa(e[i].y);
    if (p == q) continue;
    v[++ tot] = e[i].v;
    e[tot].push_back(p), e[p].push_back(tot);
    e[tot].push_back(q), e[q].push_back(tot);
	fa[p] = fa[q] = fa[tot] = tot;
}

原来的点点权为负无穷。

这样我们就得到了一棵树，这棵树就是 Kruskal 重构树。这棵树有什么性质呢？

1. 这棵树有 $2n - 1$ 个点， 以第 $2n -1$ 个点为根，该树有 $n$ 个叶子节点，叶子节点都是原来的点，因为合并操作进行了 $n - 1$ 次，原来的点显然是叶子；
2. 树上任意两点 $\tt{LCA}$ 的点权就是原图中这两点路径上最长边的最小值。这个也很显然，我们是从小到大操作边的，所以显然深度越小的点点权越大；
3. 对于原图上的一个点，它能用权值 $\le v$ 的边到达的点，就是它在树上深度最小的点权 $\le v$ 的祖先的子树内的点。这个也很显然。

根据这些性质（尤其是 2、3），$\tt{Kruskal}$ 重构树可以很好的把图上的问题转化为树上的问题。