专栏文章

Kruskal 重构树学习笔记

SSkeleton_Huo
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minng5km
此快照首次捕获于
2025/12/02 05:16
3 个月前
此快照最后确认于
2025/12/02 05:16
3 个月前
查看原文

前言

看着 rui_er 的笔记 学的。

简介

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

性质

  1. 重构树是一棵恰有 nn 个叶子节点的完满二叉树，每个非叶子节点都恰有 22 个儿子，重构树的点数为 2n−12n-1。
  2. 重构树的点权符合大根堆的性质。
  3. 原图中两点间所有简单路径的最大边权最小值，等于最小生成树上两点之间边权最大值，等于重构树上两点 LCA 的点权。
  4. 到点 uu 的简单路径上最大边权最小值 ≤k\le k 的所有节点 vv 均在重构树上的某棵子树内，且恰为该子树内的所有叶子节点。
其中 3 的证明可以考虑 Kruskal 的执行过程。4 是 3 的推论。

例题

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

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

CF1706E Qpwoeirut and Vertices

答案显然是重构树 [l,r][l,r] 的 LCA 权值，权值为边的编号。
可以直接线段树求区间 LCA。
更优秀的做法：
性质：集合 LCA 等于其中时间戳最大的点和最小的点的 LCA。
于是可以用个 ST 表求时间戳最大/小的点，然后求两点 LCA。可以做到 O(1)O(1) 查询，但是懒（

P4768 [NOI2018] 归程

虽是紫，并不难（可能是知道要用重构树）。
先对以 ll 为边权的图跑最短路，查询时是求 vv 所在的，由边权大于 pp 的边构成的连通块中，最小的 disdis。这显然可以用重构树。
以 aa 为边权的图构建最大重构树，dfs 一次算出子树中 disdis 的最大值。查询时倍增即可。

总结

一般思路：按次序连边 →\rightarrow Kruskal 算法 →\rightarrow Kruskal 重构树
Kruskal 和其重构树的关系就像点分治和点分树，KMP 算法和 KMP 自动机，分治和分治树。都是依据算法过程得到的具体结构。
一般来说能让离线做法变成在线的，即使没有在线需求，使用重构树也能让算法变简洁。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...