UPGRANET - VOI 11 (Nâng cấp mạng)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using tii = tuple<int, int, int>;

const int N = 1e5 + 5;
const int K = 25;
const int INF = 1e9 + 7;

int n, m;
vector<tii> edges;

namespace DSU {

int parent[N], sizes[N];

void reset() {
    iota(parent + 1, parent + n + 1, 1);
    fill(sizes + 1, sizes + n + 1, 1);
}

int get_parent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = get_parent(parent[x]);
}

bool join(int u, int v) {
    u = get_parent(u);
    v = get_parent(v);

    if (u == v) return false;

    if (sizes[u] < sizes[v]) swap(u, v);
    parent[v] = u;
    sizes[u] += sizes[v];
    return true;
}
} // namespace DSU

namespace LCA {

bool visited[N];
int l;
vector<pii> graph[N];
int up_cost[N][K], up_root[N][K];
int timer, time_in[N], time_out[N];

void init(int u) {
    visited[u] = true;

    for (const auto &[v, c] : graph[u]) {
        if (!visited[v]) {
            up_root[v][0] = u;
            up_cost[v][0] = c;
            init(v);
        }
    }
}

void DFS(int u) {
    time_in[u] = ++timer;
    visited[u] = true;

    for (int i = 1; i <= l; i++) {
        int mid = up_root[u][i - 1];
        up_root[u][i] = up_root[mid][i - 1];
        up_cost[u][i] = min(up_cost[u][i - 1], up_cost[mid][i - 1]);
    }

    for (const auto &[v, _] : graph[u])
        if (!visited[v]) DFS(v);

    time_out[u] = ++timer;
}

bool is_ancestor(int u, int v) {
    return time_in[u] <= time_in[v] && time_out[v] <= time_out[u];
}

int find_LCA(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;

    for (int i = l; i >= 0; i--) {
        if (up_root[u][i] == 0) continue;

        if (!is_ancestor(up_root[u][i], v))
            u = up_root[u][i];
    }
    return up_root[u][0];
}

int find_min(int p, int u) {
    int minn = 1e9;

    for (int i = l; i >= 0; i--) {
        if (up_root[u][i] == 0) continue;

        if (is_ancestor(p, up_root[u][i])) {
            minn = min(minn, up_cost[u][i]);
            u = up_root[u][i];
        }
    }
    return minn;
}
} // namespace LCA

int main() {
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#else
    freopen("UPGRADET.inp", "r", stdin);
    freopen("UPGRADET.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        edges.push_back({c, u, v});
    }
    sort(edges.rbegin(), edges.rend());

    DSU::reset();

    for (const auto &[c, u, v] : edges)
        if (DSU::join(u, v)) {
            LCA::graph[u].push_back({v, c});
            LCA::graph[v].push_back({u, c});
        }

    LCA::l = ceil(log2(n)) + 1;
    LCA::init(1);
    fill(LCA::visited + 1, LCA::visited + n + 1, false);
    LCA::DFS(1);

    int64_t ans = 0;
    for (const auto &[c, u, v] : edges) {
        int p = LCA::find_LCA(u, v);
        int minn = min(LCA::find_min(p, u), LCA::find_min(p, v));

        if (minn > c)
            ans += minn - c;
    }
    cout << ans << '\n';

    return 0;
}