Kruskal重构树.
Table of Contents
- Description
- Solution
Description
在一个无向连通图上, 每个点有长度和海拔, 对于每个询问, 从一个点出发前往1号点, 有一个水位线, 低于这个水位的都会被淹没.
可以开车途径没有被水淹没的边, 然后切换为走路. 最小化走路距离.
Solution
Kruskal重构树是对点有限制的大/小根堆.
但是这题对边有限制, 所以我们连接两个联通块的时候开一个新点.
那么这样一个点$p$的子树一定都满足$level_i > level_0$.
