题意概括

给定一个 $n$ 个点 $m$ 条边的无向连通图，边权 $w_i > 0$，可能有重边。

定义路径的代价为路径上最大边权。

对于 $u$ 到 $v$ 的路径，希望找到一条路径使最大边权最小，这个最小值记为 $f(u,v)$。

有 $q$ 个询问（$q$ 可能达到 $10^7$），每次给出 $u,v$，求 $f(u,v)$。

若 $u=v$ 则 $f(u,v)=0$。

最后输出所有询问的 $f(u,v)$ 之和模 $10^9+7$。

问题转化

$f(u,v)$ 就是 $u$ 到 $v$ 的所有路径中最大边权的最小值，即最小瓶颈路（minimum bottleneck path）问题。

在图论中，这等价于求 $u$ 和 $v$ 在最小生成树（MST） 上的路径最大边权。

为什么等价于 MST 上的路径最大边权？

定理：在无向连通图中，任意两点 $u,v$ 之间的最小瓶颈路的值等于它们在该图 MST 上的唯一路径的最大边权。

简要证明：

• 设 $T$ 是图的一棵 MST。
• 在 $T$ 中 $u$ 到 $v$ 的路径上最大边权为 $W$。
• 假设存在一条路径 $P$ 在原始图中，其最大边权 $<W$，那么可以用 $P$ 中的边替换 $T$ 中 $u-v$ 路径上权值 $\ge W$ 的某条边，得到更小的生成树，矛盾。
• 所以 $W$ 就是最小瓶颈值。

算法步骤

1. 构建最小生成树
   使用 Kruskal 算法（$O(m \log m)$），因为 $m \le 10^5$ 可行。

2. 在 MST 上预处理 LCA 与路径最大值

   • MST 有 $n-1$ 条边，是树结构。
   • 对 MST 做一次 DFS，得到每个节点的深度、父节点、以及到父节点的边权。
   • 使用倍增法（binary lifting）预处理：
     • $up[u][k]$：$u$ 的 $2^k$ 级祖先
     • $maxw[u][k]$：$u$ 到 $up[u][k]$ 路径上的最大边权

3. 回答询问 $f(u,v)$

   • 如果 $u=v$，返回 $0$。
   • 否则，找 $u,v$ 的 LCA，记为 $l$。
   • 路径 $u \to v$ 的最大边权 = $\max(\text{maxEdge}(u,l), \text{maxEdge}(v,l))$。
   • 其中 $\text{maxEdge}(u,l)$ 可以用 $maxw[u][k]$ 在 $O(\log n)$ 求出。

4. 处理大量询问
   $q$ 可达 $10^7$，$O(q \log n)$ 约 $2.4 \times 10^8$ 操作，在合理优化下可过。

复杂度分析

• Kruskal: $O(m \log m)$
• DFS + 倍增预处理: $O(n \log n)$
• 每个询问: $O(\log n)$
• 总复杂度: $O(m \log m + n \log n + q \log n)$
• 在 $n \le 70000, m \le 10^5, q \le 10^7$ 时可行

样例验证

输入：

5 7
1 2 8
2 3 9
3 1 2
3 4 7
1 4 4
3 5 6
1 4 9
10
233 17 66666 19260817

步骤 1：构建 MST

边按权值排序： (3,1,2), (1,4,4), (3,5,6), (3,4,7), (1,2,8), (1,4,9), (2,3,9)

Kruskal 过程（用并查集）：

• 选 (3,1,2)
• 选 (1,4,4)
• 选 (3,5,6)
• 选 (3,4,7) 会形成环（3-1-4-3）？检查：3-1-4 已经连通，所以跳过。
• 选 (1,2,8)
• 已选 n-1=4 条边，停止。

MST 边：
(3,1,2), (1,4,4), (3,5,6), (1,2,8)

步骤 2：回答询问

生成 $q=10$ 个询问，用给定随机函数，计算 $f(u,v)$ 并求和模 $10^9+7$。

样例输出是 32，说明这 10 个询问的 $f(u,v)$ 总和为 32。

实现细节

• 注意重边：Kruskal 时权值相同的边顺序任意，不影响 MST 的瓶颈性质。
• 随机数生成时，$u = rnd() \% n + 1$，可能 $u=v$，此时答案 0。
• 模 $10^9+7$ 只在最后求和时用，中间计算用普通整数。

总结

本题核心是最小瓶颈路 = MST 路径最大边权的经典结论，结合 LCA 与路径最大值查询，可以高效处理大量询问。