如题。
题一
· NOI 2018 D1T1
给你一张 \(n\) 个点 \(m\) 条边的无向图，每条边有长度 \(l\)，海拔 \(a\) 两个参数。
\(Q\) 次查询，每次给定一个起点 \(u\) 和当前水位线 \(p\)，你可以从 \(u\) 开始驱车经过 \(a_i > p\) 的边 \(i\) 到任意一点，然后弃车步行到 \(1\) 号点。
求最小的步行距离。\(T\) 组数据，\(n \leq 2 \times 10^5,m \leq 2 \times 10^5,Q \leq 4 \times 10^5\)，强制在线
关于 SPFA，它死了
预处理出每个点到 \(1\) 号点的最短步行距离，那么查询就变成了求当前起点 \(u\) 驱车能到达的所有点中到 \(1\) 号点的最短步行距离。
海拔的限制非常烦。我们发现如果一条边在水位线为 \(p\) 时被淹没了，那么对于任意的水位线 \(k \geq p\)，这条边都处于被淹没的状态。
考虑去刻画这个东西。
我们可以做 Kruskal 重构树，把边排序，按照海拔从高往低扫，每次合并两侧节点时，记录下新建的节点的海拔和，合并它的两个儿子到 \(1\) 号点的最短步行距离的信息。
查询的时候，往上跳到第一个海拔大于当前水位线 \(p\) 的点，那么这个点记录的信息就是从当前起点出发，驱车能到达的所有点的信息的并，直接返回记录的最短步行距离即可。
视 \(n,m,Q\) 同阶，复杂度 \(O(T \cdot n \log n)\)。
AC Code