Kruskal 重构树学习笔记

· · 算法·理论

前言

看着 rui_er 的笔记 学的。

简介

在 Kruskal 执行过程中，每次合并两个并查集的时候，建立一个虚拟节点表示合并后的并查集，其两个儿子为合并前两个并查集的对应节点。点权为边权。

性质

  1. 重构树是一棵恰有 n 个叶子节点的完满二叉树，每个非叶子节点都恰有
  2. 重构树的点权符合大根堆的性质。
  3. 原图中两点间所有简单路径的最大边权最小值，等于最小生成树上两点之间边权最大值，等于重构树上两点 LCA 的点权。
  4. 到点 u 的简单路径上最大边权最小值 \le k 的所有节点 v 均在重构树上的某棵子树内，且恰为该子树内的所有叶子节点。

其中 3 的证明可以考虑 Kruskal 的执行过程。4 是 3 的推论。

例题

P1967 [NOIP 2013 提高组] 货车运输

根据 性质 3 我们知道这是要求最大生成树上两点间简单路径的最小权，显然可以用重构树求 LCA（也可以直接倍增）。

CF1706E Qpwoeirut and Vertices

答案显然是重构树 [l,r] 的 LCA 权值，权值为边的编号。

可以直接线段树求区间 LCA。

更优秀的做法：

性质：集合 LCA 等于其中时间戳最大的点和最小的点的 LCA。

于是可以用个 ST 表求时间戳最大/小的点，然后求两点 LCA。可以做到 O(1) 查询，但是懒（

P4768 [NOI2018] 归程

虽是紫，并不难（可能是知道要用重构树）。

先对以 l 为边权的图跑最短路，查询时是求 v 所在的，由边权大于 p 的边构成的连通块中，最小的 dis。这显然可以用重构树。

以 a 为边权的图构建最大重构树，dfs 一次算出子树中 dis 的最大值。查询时倍增即可。

总结

一般思路：按次序连边 \rightarrow Kruskal 算法 \rightarrow Kruskal 重构树

Kruskal 和其重构树的关系就像点分治和点分树，KMP 算法和 KMP 自动机，分治和分治树。都是依据算法过程得到的具体结构。

一般来说能让离线做法变成在线的，即使没有在线需求，使用重构树也能让算法变简洁。