Kruskal 重构树 学习笔记

怨念终结。
前置芝士：倍增，Kruskal，LCA。
概念

问两点之间路径最长的最短/最短的最长是多少。
我们首先能想到 Kruskal 最小生成树，因为它是按照边的大小，从小往大建成一棵树的。
因为边权并不好维护，所以我们将它转换成点权。
在跑 Kruskal 的时候，对于每一条连接两个连通块的边，我们新建一个节点，连接两个连通块，并成为这个合并后的连通块在并查集中的 fa，即之后连边从这里开始。
所以最终两点的 LCA 的点权便是我们所求的最最值。
没看懂？不妨看看下面这张图，其中圆圈圈起来的是节点及其编号，圆圈外面的数字是点权。图中求的是两点路径最长的最小值：

例题

P4768 [NOI2018] 归程
首先我们看到，题目要求海拔都高于 \(p\)，那么我们的最优策略便是开车直到海拔不高于 \(p\)，此时下车走路。
那么我们用 Kruskal 重构树跑出第 \(i\) 号点到其他点的最最值 \(val\)（此处应为最大的最小值）。此时 \(i\) 号点的子树中的叶子节点都可以在水位线小于 \(val\) 的时候开车互相抵达，所以答案就是 \(v\) 的最浅的点权大于 \(p\) 的父亲节点的子树中所有叶子节点到 \(1\) 距离的最小值。
点击查看代码[code]#include#define int ll#define ll long long#define i128 __int128#define mem(a,b) memset((a),(b),sizeof(a))#define m0(a) memset((a),0,sizeof(a))#define m1(a) memset(a,-1,sizeof(a))#define lb(x) ((x)&-(x))#define lc(x) ((x)