参考：

其实Kruskal重构树并不难。

概览

首先，Kruskal重构树，顾名思义就是把整棵树重构。

并且其是基于Kruskal算法的。

它能解决很多问题，并且变种很多。

但我们先从基础的实现说起。

实现过程

我们考虑，在Kruskal算法里，我们每次会合并两个并查集集合。

准确来说是在两个点 $u$、$v$ 之间加一个边权为 $w$ 的无向边。

那么，我们就考虑，在重构树里，我们找到 $u$ 和 $v$ 分别所在的子树，把这两个子树的根拎出来，设为 $u’$ 和 $v’$。

然后，我们就新建一个点 $w$，然后把 $u’$ 和 $v’$ 的父亲设为 $w$。

此时我们就得到了另外一棵树。

比如说这个例子：

而在代码中，我们需要给这些方点一个别的编号，而不是以 $w$ 作为编号，否则会重，并且会炸。

特性

我们讲一些Kruskal重构树的特性：

  • 这棵树一定是二叉树。

  • 原树中的点放到重构树上一定是叶子，重构树上其他点都是原树中的边权。

  • 节点个数一定是 $2n-1$，且 $2n-1$ 一定是根。

  • 如果是最小生成树，那么这棵重构树一定是大根堆1，否则是小根堆。

  • 原图中两个点 $u$、$v$ 之间所有路径上的边权最大值的最小值，就是该图的最小生成树重构树上，$u$ 和 $v$​ 的LCA的权值。

    尚未想到证明方式

  • 对于一个最小生成树上的点 $x$，其只通过（边权）不超过 $v$ 的边，能到的点集；和 $x$ 在重构树上深度最浅的、权值 $\leq v$ 的点 $y$ 的子树内（叶子）节点集合，是一样的。

    这里稍微证明一下。

    就是我们根据上面的性质，可以发现，设后者对应集合为 $S$，那么显然 $S$ 内的点，和 $x$ 点，的LCA的权值一定不超过 $v$，显然。

    那根据上面那个性质，LCA不超过 $v$，那么路径上的最大权值最小值一定也不超过 $v$。

    既然如此，就证毕了。

解决题型

题型1

Kruskal重构树本来就是为了解决时间戳问题的。

题型2

比如“混合药剂”（只是猜测，因为我找不到这道题的来源）这道题就是Kruskal重构树的变种。

还比如说在正常情况下，如果要求如上面所说的「原图中两个点 $u$、$v$ 之间所有路径上的边权最大值的最小值」，那么其实可以用最小生成树。

不过这样得要写路径上最大的边权，需要用倍增。

为了防止部分人不了解，或者对下述文字出现误解或不理解，此处解释一下如何做这个倍增的。

正常情况下，如果是序列内一个区间的最大边权，那么可以用RMQ，也就是ST表（本质上就是倍增）求出。

但如果放到树上，就得稍微改一下了。

定义两个状态 $up_{x,i}$ 表示 $x$ 点向上走 $2^i$ 条边后，到达的点的编号。

还有 $ma_{x,i}$ 表示 $x$ 点往上的 $2^i$ 条边的最大边权。

那么，可以得到 $ma_{x,i}=\max(ma_{x,i-1},ma_{up_{x,i-1},i-1})$。

而求一条路径上的边权最大值，我们可以求出这条路径两端点的LCA。

随后我们把这条路径分成左右两段2处理。

然后可以发现，这个取 $\max$ 操作是可重的。

但是尽管如此，我们还得倍增，而不是像ST表一样直接求值。

具体而言，我们看 $len=dep_u-dep_t$ 的值，即 $u \to t$ 的路径长度。

然后，我们找到这个值的 $\log_2$ 值，即 $lg=\big\lfloor \log_2 (dep_u-dep_t) ~\big\rfloor$。

随后，我们可以发现，我们得求出 $u$ 往上 $len-2^{lg}$ 条边的点。

因为只有在知道这个点 $x$ 后，我们才能确定 $\max$ 的第二项。

最后我们可以直接求出答案 $\max(ma_{u,lg},ma_{x,lg})$。

那么，可以发现，这个复杂度是 $\log$ 的，跑得慢，细节多~~（不过实际上不多）~~。

不过根据上述特性，我们可以用Kruskal重构树做。

我们使用RMQ可以 $O(1)$ 在线求出任意两点的LCA值，即可 $O(1)$ 回答询问。

就是这样，我们就可以把那个 $\log$ 去掉了。

不过这样代码会长一些（我觉得实际上会长很多，不过以消掉一个 $\log$ 为获利也是很值的）

其他题型待补充

待补充

  1. 此处假设叶子节点的点权是 $-\infty$，并且我们比较的是点权，而不是代码里的节点编号（不过按理编号也是大根堆吧）。 ↩︎

  2. 设一端点为 $u$，另一端点为 $v$，LCA为 $t$，那么这两段分别为 $u \to t$ 和 $v \to t$。 ↩︎