前言
我友圈里有这样一张图（其实不是友圈，就是某一个神秘入。
25 年 S 组复赛 T2 考了 MST，赛时没想到非原图 MST 的边不具竞争力，48pts 遗憾离场，看来是该恶补一下图论了。
知周所众，我的图论非常**（确信。
记录
KRUSKAL 重构树
什么是 KRUSKAL 重构树？
现在有一张图。
考虑 Kruskal 求 MST 的过程。
1. 先对每条边排序。
2. 从小到大枚举每条边，若该边连接的两点未连通，则将该边连通。
现在我们考虑在每次连边的过程中新开一个节点，该点左右子树为该边所连接的两个点（所在子树的祖先），同时新建的节点的点权为该边边权。
如图所示：
> 说明：
> 每个非叶子节点左上角数字即为点权。
这样建出来的树就是 Kruskal 重构树。
KRUSKAL 重构树有什么用？
下面是一些常用的性质。
::::info[一些性质]{open}
说明：下列性质都是按照边权降序排序后取边的顺序所构造的重构树的性质，若按边权升序（即正常求 MST 的枚举顺序），最大/最小值互换即可。
* 结论：对于一个非叶节点 uuu，其点权必然大于其所有祖先的点权。
证明：若 uuu 的一个祖先的点权大于 uuu 的点权，则 uuu 的祖先必然先被加入重构树，成为 uuu 的子树，矛盾。
* 推论 111：对于两个叶节点 u,vu,vu,v，其在重构树上的简单路径中点权的最小值必然是两点 LCA 的点权。
证明：两点 LCA 必然是两点简单路径深度最浅的节点。
* 推论 222：对于两个叶节点 u,vu,vu,v，其在原图上所有路径边权最小值的最大值必然是两个节点的 LCA 的点权。
证明：若原图上存在一条路径边权的最小值比两点 LCA 的点权（由推论 222，该值即两点在树上的简单路径的最小值）更大，则那条边必然比两点 LCA 的点权那条边更早加入重构树，即那条边也应是重构树的一个非叶节点，矛盾。
::::
P1967 [NOIP 2013 提高组] 货车运输
由推论 222，建出重构树后求 LCA 即可。
:::success[100pts]
:::
三倍经验：P2245，P9235。
P4768 [NOI2018] 归程
注意到问题可以转化为先求出所有可以通过海拔高于 ppp 的边连通的点集，答案即为点集中所有点到 111 的最小距离。
而后者可以先提前跑一遍 Dijkstra 预处理好每个点到 111 的最小距离，前者就得用重构树。
当两个点能直接用汽车连通，必然满足两点之间存在一条边权最小值大于 ppp 的路径，换而言之，若两点所有路径边权最小值的最大值大于 ppp，则一定存在一条这样的路径，也就是一定能直接用汽车连通（代价为 000）。
故我们考虑直接从 vvv 开始往上慢慢跳，找到一个深度最浅的祖先节点，满足其点权仍大于 ppp，则所求点集即为其子树。
这一步可以用倍增加速。
::::info[略证]{}
不妨设该点为 ttt。
* 对于所有 ttt 子树内的节点，由于两点之间简单路径的最小值（因为两点的 LCA 深度一定小于 ttt，所以至少是 ttt 的点权，可能更大，不会更小）大于 ppp，故一定存在一条路径使得其所有边的海拔均大于 ppp，可以直接用汽车连通。
* 对于所有非 ttt 子树内的节点，两点之间最短路径的最小值（两点 LCA 的深度一定大于 ttt，故该值一定小于 ttt 的点权）必然不大于 ppp（若大于 ppp 则 ttt 能继续往上跳），一定无法用汽车连通。
::::
点集求出来了，到 111 的最小距离用一个简单的树形 DP 就可以实现了，每个点其子树到 111 的最小距离就是其两个子节点到 111 最小距离的最小值。
::::success[100pts]
::::
P4899 [IOI 2018] WEREWOLF 狼人
很显然对于每一个询问我们要求出从 SSS 开始人形所能到达的点集，从 EEE 开始狼形所能到达的点集，查有无交。
求两个点集可以用两颗 Kruskal 重构树解决，边权恰好为两点的最小值和最大值。
求交的话考虑用时间戳对每一个点的子树所包含的范围变为一个区间，然后扫描线离线处理一下就行了。
::::success[100pts]
::::
P7834 [ONTAK2010] PEAKS 加强版
“困难值小于等于 xxx”这个东西显然可以用 Kruskal 重构树，往上调到一个深度最浅的且点权不大于 xxx 的点，那么该点的子树内的所有叶子节点都是可以随便走的，非该点子树内的所有叶节点一定是走不到的。
注意到子树内所有叶节点的时间戳是连续的，所以问题转化为求一个区间的第 kkk 大值，套一个**树即可。
::::success[100pts]
::::
双倍经验：P4197。
P13548 [OOI 2022] AIR REFORM
这真是神仙题了。爆肝我 8days，看来还是太菜了。
大概转化一下题意：就是说给你一张无向连通图，你需要建它的一个补图，其中补图两点的边权就是在原图中两点最小瓶颈路的最大边权，你需要求出对于原图的每条边 (u,v)(u,v)(u,v)，求两点在补图中最小瓶颈路的最大边权。
对于最小瓶颈路的最大边权，这个东西显然可以用 Kruskal 重构树解决，求一个 LCA 即可。
所以算法瓶颈在于怎么快速建出补图的重构树。
考虑暴力，注意到在建原图的重构树时是从小到大枚举边权建新节点的，所以我们考虑在每次建新节点的时候枚举左右两个子树集合，若两点在原图中没有边且在补图中还未连通，则连一条边。
可以得到 21pts 的高分。
::::warning[21pts]
::::
考虑优化。
为了方便表示，对于当前节点 uuu，不妨设其左右子树分别含 idlid_lidl 和 idrid_ridr 个联通块，stxst_xstx 表示第 xxx 个连通块中的元素个数。
考虑如何合并 uuu 左右子树的连通块。
不妨先枚举左右子树的连通块 idlid_lidl 和 idrid_ridr ，用 idxidxidx 和 idyidyidy 表示，再枚举每个连通块中间的元素 stidxst_{idx}stidx 和 stidyst_{idy}stidy ，用 xxx 和 yyy 表示，若两点在原图中没有边，且在补图中尚未连通，则将两点相连（到这里和暴力是一样的）。
xxx 和 yyy 连边后，考虑将 stidyst_{idy}stidy 从 idrid_ridr 中删去，加到 stidxst_{idx}stidx 里去。
这样会存在一个问题，若左子树 idlid_lidl 内有两个连通块 idxidxidx 和 idzidzidz 内均有节点能和 idyidyidy 连通块内的节点相连，则会导致这三个连通块合并成一个大的连通块。
但我们若将 stidyst_{idy}stidy 和 stidxst_{idx}stidx 联通后直接将其加入 stidxst_{idx}stidx ，就会导致建出的树不是标准的重构树，或是建不出一个完整的树。
所以当我们处理完 stidxst_{idx}stidx 内的所有节点后，还要将 stidxst_{idx}stidx 加到 idrid_ridr 里去。
然后在做一个启发式合并，复杂度就会变成优秀的 O(nlog2n)O(n\log^2n)O(nlog2n)
正确性显然，考虑证明时间复杂度。
* 若 stidxst_{idx}stidx 和 stidyst_{idy}stidy 存在点对使得两连通块连通。显然最多只会连通 nnn 次（在补图中判连通还要乘一个 α(n)\alpha(n)α(n)），每一次联通后把两个块启发式合并，这一部分复杂度是 O(α(n)logn)O(\alpha(n)\log n)O(α(n)logn) 的。
* 若不能连通，则枚举完 stidyst_{idy}stidy 后，会将 stidxst_{idx}stidx 加到 idrid_ridr 里，注意到这里也是用启发式合并的，一个点最多会被加入 logn\log nlogn 次。
同时每次查一下在原图是否有边也是 logn\log nlogn 的。
所以建补图重构树的复杂度是 O(mlog2n+mα(n)logn)O(m\log^2n+m\alpha(n)\log n)O(mlog2n+mα(n)logn)。
其余部分复杂度显然没有建补图的复杂度大，直接忽视即可。
::::success[100pts]
::::
