不支持时间旅行的可持久化并查集

　　给定 n 个点, 以及 m 次操作, 操作有两种:

　　　　① 将点 x 与点 y 进行连边;

　　　　② 询问在前 t 次操作操作中, x 与 y 是否连通.

　　n <= 100000, 强制在线.

核心模型

　　n 个点, m 条带权边的无向图.

　　多次询问点 x 和点 y 在边权不超过 w 的边的作用下的连通性信息(例如, 是否连通).

　　强制在线.

　　对于不支持时间旅行的并查集问题, 将时间这一维给量化之后, 可以等价地看成这个核心模型.

　　对于操作①, 我们相当于连边 (x, y) , 边权为 t .

　　对于操作②, 相当于查询边权不超过 t 的边的作用下, x 和 y 是否连通.

问题解决

　　假如可以离线, 那么我们就有 Kruskal + 并查集 的做法.

　　从小到大, 每连接一条边, 就将连接下一条边前的询问进行回答.

　　现在要求在线, 我们尝试维护历史版本的并查集.

　　我们考虑在并查集存储更多的信息, 从而也使用更适合的按秩合并的方法, 而不使用更快的路径压缩的方法.

　　将点 x 的父亲设为 y 的时候, 我们考虑多记录 w 数组, w[x] = 当前连边的边权.

　　我们当前要查找在不超过 d 的边权的作用下, x 在并查集的代表元素.

　　我们从查询的点开始跳, 当且仅当 d >= w[x] , 那么代表元素是 x 的祖先.

　　如此下来, 我们能找到并查集的代表元素, 且复杂度为 O(n log n) .

Kruskal重构树

　　我们把利用 f[], w[] 两个数组构建出来的树叫做 Kruskal重构树 .

　　我们可以轻易地查询在边权不超过 d 的边的作用下, x 对应的并查集的代表元素 a . 我们还可以知道更多的信息, 因为与 x 连通的元素的集合就是 a 的子树对应的集合.

　　所以, 这棵树的作用可以概括为: 询问 x 在边权不超过 d 的边的作用下的连通性信息.

　　以强制在线 Peaks 一题为例.

　　给定一张图, m 次询问 (x, k): 在边权不超过 d 的边的作用下, 与 x 连通的所有点中点权第 k 小是多少?

　　我们考虑利用并查集构建出 Kruskal 重构树, 我们找边权不超过 d 的边的作用下, x 的代表元素 a , 那么相当于查询子树 a 的所有点的点权第 k 小.

Kruskal重构树