思路与算法

用Kruskal构造最小生成树，再在树上预处理倍增祖先及每个上跳块的最大边。询问S,T先抬平深度，再同时上跳到LCA下方，合并所有跳过边的最大值。

正确性说明

MST路径上的最大边e删去后把两端分开，任何原图路径都跨越该割；若有一条跨割边权小于e，可替换使生成树更轻，矛盾。故任何原图路径瓶颈至少为树路径最大边，而该树路径本身可行，等号成立。倍增按路径分块取max精确。

复杂度

排序O(MlogM)，并查集近线性；建树与遍历O(N+M)，倍增初始化O(NlogN)，Q询问O(QlogN)。空间O(M+NlogN)。

易错点

允许0权、重边和自环；Kruskal自然跳过无用自环。城市保证连通。同城不走道路，无过路费，输出0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    vector<int> p, s;
    DSU(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int f(int x) {
        while (x != p[x]) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    bool join(int a, int b) {
        a = f(a);
        b = f(b);
        if (a == b)
            return false;
        if (s[a] < s[b])
            swap(a, b);
        p[b] = a;
        s[a] += s[b];
        return true;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> e;
    while (m--) {
        int a, b, w;
        cin >> a >> b >> w;
        e.emplace_back(w, --a, --b);
    }
    sort(e.begin(), e.end());
    DSU ds(n);
    vector<vector<pair<int, int>>> g(n);
    for (auto z : e) {
        int w, a, b;
        tie(w, a, b) = z;
        if (ds.join(a, b)) {
            g[a].push_back({b, w});
            g[b].push_back({a, w});
        }
    }
    int K = 1;
    while ((1 << K) <= n)
        K++;
    vector<vector<int>> p(K, vector<int>(n)), mx = p;
    vector<int> dep(n, -1), ord(1, 0);
    dep[0] = 0;
    for (size_t i = 0; i < ord.size(); i++) {
        int u = ord[i];
        for (auto v : g[u])
            if (dep[v.first] < 0) {
                dep[v.first] = dep[u] + 1;
                p[0][v.first] = u;
                mx[0][v.first] = v.second;
                ord.push_back(v.first);
            }
    }
    for (int k = 1; k < K; k++)
        for (int i = 0; i < n; i++) {
            p[k][i] = p[k - 1][p[k - 1][i]];
            mx[k][i] = max(mx[k - 1][i], mx[k - 1][p[k - 1][i]]);
        }
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        int ans = 0;
        if (dep[a] < dep[b])
            swap(a, b);
        for (int k = K - 1; k >= 0; k--)
            if ((dep[a] - dep[b]) >> k & 1) {
                ans = max(ans, mx[k][a]);
                a = p[k][a];
            }
        if (a != b) {
            for (int k = K - 1; k >= 0; k--)
                if (p[k][a] != p[k][b]) {
                    ans = max(ans, max(mx[k][a], mx[k][b]));
                    a = p[k][a];
                    b = p[k][b];
                }
            ans = max(ans, max(mx[0][a], mx[0][b]));
        }
        cout << ans << '\n';
    }
}