Kruskal 重构树学习笔记

Kruskal 重构树,顾名思义,就是利用 Kruskal 算法构造出的一棵新树。

(好像是句废话)

构造方式

给出一张图,构造其 Kruskal 重构树的方式和用 Kruskal 求其最小生成树的方式其实是差不多的。

我们维护一个 \(n\) 个点构成的森林。刚开始这个森林中没有一条边,每个点的点权均为 \(0\)。

接下来我们按照 Kruskal 的方式,从小到大考虑每条边。

对于一条边 \(u \to v\),设 \(u\) 的树根为 \(ru\),\(v\) 的树根为 \(rv\)。

如果 \(u\) 和 \(v\) 不在一棵树中,就新建一个点 \(p\),\(p\) 的点权设为这条边的边权,然后连接 \(p \to ru\),\(p \to rv\)(将 \(u\) 和 \(v\) 所在的集合并入新集合中)。

最后我们会得到一棵 \(2n-1\) 个点的树,这就是 Kruskal 重构树。

这棵树有什么特点呢?

  1. 整棵树都是二叉树,并且任意一个非叶子节点都有两个儿子(可以从合并过程来看出来);
  2. 整棵树满足大根堆性质,即任意一个点的点权都比其子节点的点权大(仍然考虑合并过程);
  3. 原图的最小生成树上两点间路径中的最大边权,等于重构树上两点最近公共祖先的点权(还是可以从合并过程中看出来)。

例题

可以拿来做一道 Kruskal 重构树的练手题。

建立最大生成树的 Kruskal 重构树(因为不保证联通,所以严格来说是重构森林),根据上面的性质 3,答案即为 \(\text{lca}(u,v)\)。

记得判断 \(u,v\) 不联通的情况。

代码在上面的题解里,这里就不贴了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注