lessons/参考实现/06-最小与最大生成树/CodeForces-609E.cpp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
struct DSU {
    vector<int> p, s;
    explicit DSU(int n) : p(n), s(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b); if (a == b) return false;
        if (s[a] < s[b]) swap(a, b); p[b] = a; s[a] += s[b]; return true;
    }
};
struct Edge { int u, v; long long w; bool tree = false; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<Edge> edges(m); vector<int> order(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        --edges[i].u; --edges[i].v; order[i] = i;
    }
    sort(order.begin(), order.end(), [&](int a, int b) { return edges[a].w < edges[b].w; });
    vector<vector<pair<int, long long>>> tree(n);
    DSU dsu(n); long long total = 0;
    for (int id : order) if (dsu.unite(edges[id].u, edges[id].v)) {
        edges[id].tree = true; total += edges[id].w;
        tree[edges[id].u].push_back({edges[id].v, edges[id].w});
        tree[edges[id].v].push_back({edges[id].u, edges[id].w});
    }
    constexpr int log = 20;
    vector<vector<int>> up(log, vector<int>(n));
    vector<vector<long long>> maximum(log, vector<long long>(n));
    vector<int> depth(n, -1); queue<int> q; depth[0] = 0; up[0][0] = 0; q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : tree[u]) if (depth[v] == -1) {
            depth[v] = depth[u] + 1; up[0][v] = u; maximum[0][v] = w; q.push(v);
        }
    }
    for (int j = 1; j < log; ++j) for (int v = 0; v < n; ++v) {
        up[j][v] = up[j - 1][up[j - 1][v]];
        maximum[j][v] = max(maximum[j - 1][v], maximum[j - 1][up[j - 1][v]]);
    }
    auto path_max = [&](int u, int v) {
        long long answer = 0;
        if (depth[u] < depth[v]) swap(u, v);
        for (int j = log - 1; j >= 0; --j) if (depth[u] - (1 << j) >= depth[v]) {
            answer = max(answer, maximum[j][u]); u = up[j][u];
        }
        if (u == v) return answer;
        for (int j = log - 1; j >= 0; --j) if (up[j][u] != up[j][v]) {
            answer = max({answer, maximum[j][u], maximum[j][v]});
            u = up[j][u]; v = up[j][v];
        }
        return max({answer, maximum[0][u], maximum[0][v]});
    };
    for (const Edge &e : edges) {
        cout << (e.tree ? total : total + e.w - path_max(e.u, e.v)) << '\n';
    }
}