货车运输：题解

思路

一条路径的载重上限是路径最小边权，询问要在所有路径中最大化这个值。将边按权值降序做 Kruskal，得到最大生成森林。任意两个连通顶点在森林唯一路径上的最小边权，正是原图最大瓶颈值。

做法

对最大生成森林的每棵树分别选根，预处理每个顶点的 $2^k$ 级祖先，以及跳到该祖先路径上的最小边权。询问时先判断连通性；若连通，先将较深顶点提升到同深度，再同时提升两点直到最近公共祖先，并对经过的所有边权取最小值。

正确性证明

设森林中两点路径最小边权为 $w$。删去该边后两点分属一个割的两侧。Kruskal 在权值 $w$ 时才连通这两侧，所以原图不存在所有边权都大于 $w$ 的跨割路径。森林路径自身又能实现 $w$，故 $w$ 是最大瓶颈值。倍增过程覆盖两点到 LCA 的全部边且无遗漏，因而取得的最小值正是森林路径瓶颈。不同连通块没有路径，输出 $-1$。

复杂度分析

时间复杂度为 $O(m\log m+(n+q)\log n)$，空间复杂度为 $O(m+n\log n)$。

部分分算法

对 $n\le200$，用 max-min Floyd 直接求所有点对的最大瓶颈，复杂度 $O(n^3+q)$。对 $n,q\le999$，先建最大生成森林，每个询问沿树路径 DFS，复杂度 $O(m\log m+nq)$。