道路阻断(Disruption P) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

struct ExtraEdge {
    int u, v, w;
    bool operator<(const ExtraEdge& o) const { return w < o.w; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    vector<int> par(n + 1, 0), dep(n + 1, 0), pe(n + 1, -1), q;
    q.reserve(n);
    q.push_back(1);
    dep[1] = 1;
    for (int idx = 0; idx < (int)q.size(); ++idx) {
        int u = q[idx];
        for (auto [v, eid] : adj[u]) {
            if (!dep[v]) {
                dep[v] = dep[u] + 1;
                par[v] = u;
                pe[v] = eid;
                q.push_back(v);
            }
        }
    }
    vector<ExtraEdge> ex(m);
    for (int i = 0; i < m; ++i) cin >> ex[i].u >> ex[i].v >> ex[i].w;
    sort(ex.begin(), ex.end());
    vector<int> dsu(n + 1);
    iota(dsu.begin(), dsu.end(), 0);
    auto find = [&](int x) {
        while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]];
        return x;
    };
    vector<int> ans(n - 1, -1);
    for (const auto& e : ex) {
        int u = find(e.u), v = find(e.v);
        while (u != v) {
            if (dep[u] < dep[v]) swap(u, v);
            ans[pe[u]] = e.w;
            dsu[u] = find(par[u]);
            u = dsu[u];
        }
    }
    for (int i = 0; i < n - 1; ++i) cout << ans[i] << "\n";
    return 0;
}