资讯详情

link

题意

你有一个 \(n\) 个点 \(m\) 条边的无向图。每个边有边权。

\(q\) 次查询，给出出发点 \(u\) 和权值 \(k\)，你可以先只经过边权 \(\gt k\) 的边到一个点 \(v\)，然后从这个点到 \(1\)，代价为你从 \(v\) 到 \(1\) 的路径长度。
最小化代价。

思路

看到边权 \(\gt k\)，容易想到 Kruskal 重构树。按照最大生成树建出重构树，我们在树上跳到深度最小的一个点，满足这个点的点权 \(\gt k\)，然后这个点的子树内的点显然都能到达。
由于 Kruskal 重构树的性质，祖先权值严格大于孩子的权值，所以这可以通过树上倍增实现。

显然固定 \(v\) 的情况下，最小化代价就要走 \(v\) 到 \(1\) 节点的最短路。
那么我们就要找到重构树上一个子树内的 \(v\)，满足 \(dis_{v \rightarrow 1}\) 最小。
这并不难实现，我们在建树前预处理 \(1\) 到其他点的单源最短路长度，然后在建树时维护一个点子树内的 \(\min dis\) 即可。

时间复杂度 \(\mathcal{O}((n + m) \log n)\)