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\) 不联通的情况。

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

我们要找的是起点 \(s\) 能到达的所有点中,距离 \(1\) 号点最近的点。

先预处理 \(1\) 至其他点的最短路,随后以海拔为关键字降序排列所有边,建立 Kruskal 重构树。建树时同时处理一个点的所有子节点距离 \(1\) 号点的最近距离。

如果一个点 \(u\) 的点权大于水位线,则 \(u\) 子树内的所有点互相可达。

因此我们需要找到 \(s\) 的一个深度最浅的祖先,使得该祖先的点权高于水位线。这个可以通过树上倍增实现。

代码详见上面贴的题解。

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据