P1967 [NOIP 2013 提高组] 货车运输

2025-05-27

看着不太会，于是果断打开题解。果然稍微有点难想，需要树上倍增求LCA，我不咋熟，也是后面基本没用过。树剖还稍微写了几题。

tag: LCA 生成树 倍增

hhh，还有好多篇博客没有写，很多题目没有补，也快要期末考试了，下周是最后一个有课的周，端午打算回家玩玩。

题意

给一个 \(n\) 个点 \(m\) 条边的无向图，有 \(q\) 次询问，每次询问 \(x\) 到 \(y\) 的路径经过的最小边权最大是多少。

思路

如果是一个树，那就很好考虑路径问题，但是图就不好搞。但这题，只需要考虑路径上的最小的边，可以把这个图上很多无用的边去掉，只需要保留最大生成树。还有哪些情况可以像这样转换呢？然后就变成树上的问题了，两点之间的路径变成了唯一的，只需要 LCA 来求路径，预处理一下经过的最小的边。

代码

lca 代码还挺好懂的，就是先让两个点深度相同，然后若它们深度相同后仍为不同的点，那么它们的 lca 在深度更小的节点。这里使用 \(e_{u,i}\) 来求 \(u\) 到第 \(2^{i}\) 个祖先的路径上经过的最短的边，跟 lca 一样的。

// #define YUANSHEN
#if defined(YUANSHEN)
#include "C:/codes/cp_code/template/debug.hpp"
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) 42
#endif

#define rep(N) for(int i = 1; i <= N; i++)

template <typename T1, typename T2>
void cmin(T1& x, const T2& y)
{
    x = x < y ? x : y;
}
template <typename T1, typename T2>
void cmax(T1& x, const T2& y)
{
    x = x > y ? x : y;
}
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using vc = vector<T>;

#define fixset(x) fixed << setprecision(x)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ALL(x) (x).begin() + 1, (x).end()
constexpr int INF = 1000000000;
constexpr ll LNF = 1000000000000000000LL;

// Date: 2025-05-27
// Time: 17:01:29
int fa[10005][21], e[10005][21];

void ChatGptDeepSeek()
{
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edge(m);
    for(int i = 0; i < m; i++)
        cin >> edge[i][0] >> edge[i][1] >> edge[i][2];
    vi f(n + 1);
    vc<vc<array<int, 2>>> g(n + 1);
    auto find = [&](auto &&self, int x) -> int{
        return f[x] == x ? x : f[x] = self(self, f[x]);
    };
    auto kruskal = [&](){
        ranges::sort(edge, [](array<int, 3> x, array<int, 3> y){
            return x[2] > y[2];
        });
        for(int i = 1; i <= n; i++)
            f[i] = i;
        for(auto [u, v, w] : edge){
            if(find(find, u) != find(find, v)){
                f[f[v]] = f[u];
                g[u].push_back({v, w});
                g[v].push_back({u, w});
            }
        }
    };
    kruskal();
    vi dep(n + 1);
    auto dfs = [&](auto &&self, int u, int pre) -> void{
        dep[u] = dep[pre] + 1;
        for(auto [v, w] : g[u]){
            if(v == pre) continue;
            fa[v][0] = u, e[v][0] = w;
            self(self, v, u);
        }
    };

    for(int i = 1; i <= n; i++){
        if(dep[i] == 0){
            dfs(dfs, i, 0);
            fa[i][0] = i;
            e[i][0] = INF;
        }
    }
    for(int i = 1; i <= 20; i++){
        for(int j = 1; j <= n; j++){
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
            e[j][i] = min(e[j][i - 1], e[fa[j][i - 1]][i - 1]);
        }
    }
    auto lca = [&](int x, int y){
        if(find(find, x) != find(find, y)) return -1;
        if(dep[x] < dep[y]) swap(x, y);
        int res = INF;
        for(int i = 0, z = dep[x] - dep[y]; z; i++, z >>= 1){
            if(z & 1){
                cmin(res, e[x][i]);
                x = fa[x][i];
            }
        }
        if(x == y) return res;
        for(int i = 20; x != y && i >= 0; i--){
            if(fa[x][i] != fa[y][i]){
                cmin(res, min(e[x][i], e[y][i]));
                x = fa[x][i], y = fa[y][i];
            }
        }
        cmin(res, min(e[x][0], e[y][0]));
        return res;
    };
    int q;
    cin >> q;
    while(q--){
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
}

int main()
{
#ifndef YUANSHEN
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#endif
    int T = 1;
    // cin >> T;
    while (T--)
        ChatGptDeepSeek();
    return 0;
}