Kruskal 重构树
这是一种用于处理与最大/最小边权相关的一个数据结构。
其与 kruskal 做最小生成树的过程是类似的，我们考虑其过程：
按边权排序，利用并查集维护连通性，进行合并。
如果我们在合并时，新建一个节点，其权值为当前处理的边的权值，并将合并的两个节点都连向新建的节点，那么就可以得到一颗重构树。
例如下列数据生成的重构树：
4
1 4 2
2 3 4
1 3 1
3 4 3
黑色代表节点编号，红色代表其权值。
其满足一些性质：
这是一个二叉树，也是一个二叉堆
两点 $\mathrm{LCA}$ 的权值即是这两点联通的 最小/最大 代价/时间。
对于一个限制，找到某个点最高的祖先 $S$ 满足这个限制，那么 $S$ 所在子树都满足此限制，并且此子树下所有叶节点在此限制下全部联通。
由于这些性质，kruskal 重构树常常与树剖/树上倍增放一起，做到每次 $O(\log n)$ 的神秘操作。
以 Qpwoeirut and Vertices - 洛谷 为例：
给出 $n$ 个点，$m$ 条边的不带权无向连通图，$q$ 次询问至少要加完前多少条边 $[L, R]$ 中的所有节点联通。
这是非常板的题，边权也就是其编号。
设 $f(x)$ 表示 $x$ 和 $x + 1$ 联通的时间，那么所求也就是 $\max_{x = L}^{R - 1} f(x)$，这只需要求出 $f(x)$ 随便维护一下即可。
那么求 $x, x + 1$ 的联通时间，找到他们在重构树上的 $\mathrm{LCA}$，返回其编号即可。
或许其考点就是知不知道重构树，如果会了重构树，那么就简单了。
按照边权从大到小建出重构树，那么在当前水位下可联通的部分（整棵子树）也就很好求。
求这部分到固定的终点的最短路径？跑一次 DJK，然后把重构树看作一颗线段树，节点保存的也就是子树内最小的距离，在查询的时候利用倍增跳一跳就行了。
另一种打开方式 - 基于点权的 kruskal 重构树
我们从这道题开始：
给定一颗树，认为一条从 $x \to y$ 的简单路径是好的，当且仅当路径上的点中编号最小的是 $x$，最大的是 $y$。计数好的简单路径条数。
有一种解决方法是利用笛卡尔树，然而我并不是很会，所以不管了。
这里发现没有我们熟悉的边权了，但是我们仍然可以考虑类似的过程，首先按照点权排序，这里不妨设为从小到大。
那么我们依次遍历 $x$，如果此时遍历到了一个边 $(x, y)$ 满足 $w_x > w_y$，那么将 $x$ 作为 $y$ 所在的树的根的父亲（也就是并查集合并的过程，合并完之后其实就是一个重构树）
可以发现，这样，$\mathrm{lca}(x, y)$ 的点权也就是原树上两点路径间的最大权值。
同理，在这道题中建出从大到小的树，那么 $(x, y)$ 能够做出贡献当且仅当在一棵树上 $x$ 作为 $y$ 的祖先，并且在另外一颗树上 $y$ 是 $x$ 的祖先。
于是在一棵树上加，另一棵树上遍历即可。
# [IOI2018] werewolf 狼人
我们通过这道经典的题目细致的讲一讲如何构造点权的重构树。
题意中的路径需要满足前面部分 $\ge L_i$，后面部分 $\le R_i$，我们按照点编号大小构建两棵重构树，第一棵是最小联通标号，第二则是最大。
这是原树：
我们先构造第一棵，也就是最小联通标号，那么此时我们需要从编号大的作为叶子开始，一点一点构建这个树。
首先加入 $5$ 节点，没有已经加入的节点，则加入 $4$，同理，则加入 $3$，发现此时 $4$ 存在，并且其所在树的根为 $4$，则将 $3$ 作为 $4$ 的根：
此时继续加入 $2$，没有连着已经加入的节点，继续加入 $1$，发现 $1$ 与 $5, 2, 3$ 相连，那么将 $1$ 作为他们所在子树的根即可：
最后加入 $0$，发现与 $3$ 相连，则 $0$ 作为 $3$ 所在的子树的根的父亲即可：
此时，我们构造出的这棵重构树满足两点的 $lca$ 即他们在原树上路径间的最小值，除了不是一棵二叉树，性质与边权重构的树性质类同。
同理，我们可以构造出另一棵树：
于是问题转化为在求两棵树上两个子树是否有交，这不是本文的重点，略。
这部分的代码大概就是：
mfs.init(n);
for (int x = 0; x < n; ++x) {
for (int y : T[0].G[x]) {
// 如果还没有加入或者已经联通就跳过
if (y > x || mfs.find(x) == mfs.find(y)) continue;
T[1].add(x, mfs.find(y)); // 注意这里是 x 作为 find(y) 的父亲！
mfs.merge(y, x); // 注意这里是 grp[find(y)] = x !!!
}
}
然而事实上我们可以不用如此，完全可以直接将点权下方到边权即可。
在这道题来说，如果是构建第一棵树，那么边权设为 $\min(x, y)$ 即可。
构造出来的树即是：
可以看见构建顺序不同……但是很像！就是把相同的点缩起来了……QwQ
不过感觉第一种写法在处理一些东西的时候方便很多。
作者有话说
对于重构树的另一种打开方式我并没有在其他地方看到过，毕竟它并没有什么特别突出的点使得它可以代替边权的重构树，甚至在重构出来的形态 - 非二叉树上劣于边权的重构树。
不过这个思想还是蛮不错的。