关于 spfa ……
题意
给定 $n \le 2 \times 10^5$ 个点的图，每条边有海拔 $h_i$ 和长度 $l$ ，有 $q \le 4 \times 10^5$ 次询问，每次给定 $v, p$ ，询问只保留 $h_i \ge p$ 的边的情况下，从 $v$ 出发能走到的点 $u$ 中到点 $1$ 距离最小的点，输出最小距离，强制在线
关于 spfa
一位巨佬用血的教训告诉我们，它死了
所以，我们用 dijkstra 求出点 $1$ 到每个点的最短距离，记作 $dis_i$ ，时间为 $O(m \log n)$
kruskal 重构树
好像说还有可持久化并查集的做法，但我不会，所以用 kruskal 重构树
考虑我们 kruskal 的过程，每次我们取出边权最小的边，用并查集判断两边的联通性，如果不联通就合并并查集（相当于选边）
在以上过程中，因为构造最小生成树过程中树的形状和中途选边的顺序对我们来说不重要，所以我们放弃了这些信息，用路径压缩优化了时间
但现在，如果我们要保留这些信息呢？具体的：
- 把所有边排序，记边为 $(x, y, z)$ ，表示 $x \to y$ ，权为 $z$
- 构建 $n$ 个无权点，没有边
- 每次取出一条边 $(x, y, z)$ ：
- 若 $x, y$ 联通（在同一棵树），不管它
- 否则，新建一个节点 $t$ ，记 $x, y$ 所在树的根为 $r_x, r_y$ ，让 $t$ 的左右儿子分别为 $r_x, r_y$ ，并让 $t$ 的点权为 $z$
不难发现 kruskal 重构树有如下性质：
- 它是一棵二叉树（更进一步，它其实就是个二叉堆），树上除叶子结点以外的点都对应着原来生成树中的边，叶子结点就是原来生成树上的节点
- 除叶节点外，儿子节点对应边一定排序在父亲前面，即从每个点到根节点上除叶子结点外按顺序访问到的点的点权是单调的
- 对于叶节点 $x, y$ ， $lca(x, y)$ 对应的边就是最小生成树中联通 $x, y$ 的“瓶颈边”（它排序在最后）
kruskal 重构树的构建可以在 kruskal 的基础上进行，时间 $O(m \log m)$
思路
那么，我们如何用重构树做本题呢？
首先，我们把边按 $h_i$ 降序排序（边的长度 $l$ 在我们求出 $dis$ 数组后就没有用了），然后建出重构树
由重构树的性质，我们知道，对于点 $x, y$ ， $lca(x, y)$ 对应的边就是连接 $x, y$ 的边中海拔最小的，那么对于每次询问 $v$ ，我们就是要找到所有的 $u$ 满足 $h_{lca(u, v)} \ge p$ ，答案就是 $\min(dis_u)$
但直接每个点找肯定是不行的，根据重构树的性质， $x$ 子树中的所有点（除了叶子）的海拔都高于 $x$ ，所以如果 $h_x \ge p$ ，那么它的子树一定都高于 $p$ ，我们可以用树上倍增找到 $v$ 的祖宗中最浅的（即子树最大的）满足 $h_x \ge p$ 的 $x$ ，它子树中的任意一个点 $u$ 都是满足 $h_{lca(u, v)} \ge p$ 的，且不在它子树里面的点一定不满足（因为那些点和 $v$ 的 $lca$ 只会在 $x$ 的上面），那么问题就化为了子树 $\min$ ，预先统计即可
时间 $O(T(m + q) \log m)$
代码
1 |
|