百年一遇的AC

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

const int MAXN = 1e5 + 5; const int LOG = 20;

struct Edge {

int u, v, w;
bool selected;

};

vector edges; vector<pair<int, int>> adj[MAXN]; int fa[MAXN][LOG]; int maxw[MAXN][LOG]; int depth[MAXN];

struct DSU {

vector<int> parent, rank;
DSU(int n) {
    parent.resize(n + 1);
    rank.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        rank[i] = 1;
    }
}
int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (rank[x] < rank[y]) parent[x] = y;
    else {
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
    return true;
}

};

void build_parent(int n) {

queue<int> q;
q.push(1);
memset(depth, 0, sizeof(depth));
depth[1] = 1;
fa[1][0] = 0;
maxw[1][0] = 0;

while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto &[v, w] : adj[u]) {
        if (!depth[v]) {
            depth[v] = depth[u] + 1;
            fa[v][0] = u;
            maxw[v][0] = w;
            q.push(v);
        }
    }
}

}

int lca(int u, int v) {

if (depth[u] < depth[v]) swap(u, v);
for (int k = LOG - 1; k >= 0; --k)
    if (depth[u] - (1 << k) >= depth[v])
        u = fa[u][k];
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k)
    if (fa[u][k] != fa[v][k])
        u = fa[u][k], v = fa[v][k];
return fa[u][0];

}

int get_max_edge(int u, int p) {

int max_edge = 0;
while (depth[u] > depth[p]) {
    int k = log2(depth[u] - depth[p]);
    max_edge = max(max_edge, maxw[u][k]);
    u = fa[u][k];
}
return max_edge;

}

int main() {

ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m;
cin >> n >> m;
edges.resize(m);
for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    edges[i] = {u, v, w, false};
}

sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
    return a.w < b.w;
});

DSU dsu(n);
long long sum = 0;
for (Edge &e : edges) {
    if (dsu.unite(e.u, e.v)) {
        sum += e.w;
        e.selected = true;
        adj[e.u].emplace_back(e.v, e.w);
        adj[e.v].emplace_back(e.u, e.w);
    }
}

build_parent(n);

for (int k = 1; k < LOG; ++k) {
    for (int u = 1; u <= n; ++u) {
        fa[u][k] = fa[fa[u][k-1]][k-1];
        maxw[u][k] = max(maxw[u][k-1], maxw[fa[u][k-1]][k-1]);
    }
}

long long ans = LLONG_MAX;
bool found_equal = false;

for (const Edge &e : edges) {
    if (!e.selected) {
        int u = e.u, v = e.v, w = e.w;
        if (dsu.find(u) != dsu.find(v)) continue;

        int p = lca(u, v);
        int max1 = 0, max2 = 0;

        int curr = u;
        while (depth[curr] > depth[p]) {
            int k = log2(depth[curr] - depth[p]);
            max1 = max(max1, maxw[curr][k]);
            curr = fa[curr][k];
        }

        curr = v;
        while (depth[curr] > depth[p]) {
            int k = log2(depth[curr] - depth[p]);
            max2 = max(max2, maxw[curr][k]);
            curr = fa[curr][k];
        }

        int current_max = max(max1, max2);

        if (w == current_max) {
            found_equal = true;
            break;
        } else if (w > current_max) {
            ans = min(ans, sum - current_max + w);
        }
    }
}

if (found_equal) {
    cout << sum << "\n";
} else {
    cout << (ans == LLONG_MAX ? sum : ans) << "\n";
}
return 0;

}