NOI2018 归程

发布于 2021-07-11 | 分类于随笔 | 1分钟 | 94字数

kruskal 重构树板子题。
以海拔从高到低建树，海拔越高节点深度越深。
倍增寻找最后一个不会被水淹没的道路，直接输出子树中距离 $1$ 最小的点的距离即可。
距离可以用 dijkstra 预处理。
这道题倍增的时候常数开到 $19$ 就差不多了，开大了会 T。