首先要知道一种叫做克鲁斯卡尔求最值生成树的东西

在实现 (Kruskal) 算法的时候，进行并查集操作的时候，要注意到要合并两个子树

这时候我们可以像线段树的 (push\_up) 一样来维护一些量，比如权值等等

构建的时候就是在并查集的合并新建一个节点，然后把点的权值记录成要维护的极值，所以如果查询图上的类似信息，可以考虑 (LCA)

或者以下问题

“经过图上不超过一个给定值能达到的最远的边”

（画一棵树模拟一下你就知道咋做了）

”两个点之间经过路径最长边的最小值“（bzoj3732）

（好像是最小生成树完了 (LCA)）

都是可以考虑用这个算法解决的

但是解决的问题的范围还是有限，最多是一些”最大最小“同时出现的，或者离线可二分的东西

建出来的生成树有一些性质：

(1.) 因为克鲁斯卡尔，所以每个点到根经过路径上的点权是单调的

(2.) 树上除了叶子节点是一一对应原来图上的点之外，别的所有点是对应树上的边

(3.) 克鲁斯卡尔重构树是棵二叉树

(4.) 如上面的解决的问题所说，图上面任意两个节点某种权值的瓶颈就在它们的 (lca)

Description

题面细节相对多，建议去链接中阅读

Solution

首先发现这里限制了一个维度（海拔）

就是先按照海拔从大到小排个序，扔到重构树里面

这里的重构树是一个小根堆，如果走到小于海拔限制的就不能走了

每次查询，直接从重构树上面往上走，走到那个超过海拔限制的点结束

这部分需要树上倍增

然后该点的子树里面的所有点都是可以直接坐车到的

然后考虑的就是找到这些点里面到 (1) 距离的最小值

直接 (dfs) 解决掉就好了

还是一道运用性质的不错的题目

就像 (NOI2013) 是删掉基环树上一条边后求直径的最小值一样

代码慢慢打吧

然后是下一道例题：

IOI2018狼人

其实相对而言比较好说

首先克鲁斯卡尔重构树维护可以走到的点，建一个大根的，一个小根的

然后在以两个点为根的子树里面求交集

如果有交集，那么就是 (1)

否则就是 (0)

树的子树求交集问题？

先求出来 (dfs) 序，然后以 (d_A) 为下标，(d_B) 为权值建主席树

然后查询的本质就是跳 (father) 和二维数点