离线+并查集

LCA&DSU&MST - jzcrq - 博客园 (cnblogs.com)

多次询问两点间的瓶颈路，也就是u到v所有路径中边权的最小值最大。

Sol：考虑先将所有询问离线。考虑建立最大生成树的过程，设联通块s1和s2要被边权为w的边连通。对于存在点u在s1,v在s2的询问的答案就是w。为了保证时间复杂度我们考虑启发式合并，注意判断大小的时候只需要交换u和v本身。把询问的对应点和编号挂在点上，每次把size小的部分的点拿出来更新答案和询问。无法回答的插入新的根中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void solve() {
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edg(m + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edg[i] = {w, u, v};
    }
    int q;
    cin >> q;
    vector<vector<pii>> qv(n + 1);
    for (int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        qv[u].push_back({v, i});
        qv[v].push_back({u, i});
    }
    sort(edg.begin() + 1, edg.end(), [](auto i, auto j) {
        return i[0] > j[0];
    });
    DSU dsu(n);
    vector<int> ans(q + 1, -1);
    deb(edg);
    for (int i = 1; i <= n; i++) deb(i, qv[i]);
    for (int i = 1; i <= m; i++) {
        auto [w, u, v] = edg[i];
        deb(w, u, v);
        u = dsu.find(u), v = dsu.find(v);
        deb(u, v);
        if (u == v) {
            continue;
        } else {
            if (qv[v].size() > qv[u].size()) {
                swap(u, v);
            }
            deb(v, qv[v]);
            for (auto [nx, id] : qv[v]) {
                deb(v, nx, id);
                deb(ans[id]);
                if (ans[id] > 0)
                    continue;
                if (dsu.find(nx) == u)
                    ans[id] = w;
                else
                    qv[u].push_back({nx, id});
            }
            dsu.merge(u, v);
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << endl;
}