求调玄一关 84pts

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, fa[100005], head[100005], sum, mi = INT_MAX, ans, vis[100005];
int dep[100005], w1[100005][25], w2[100005][25], f[100005][25];
struct node {
    int x, y, z;
} edge[300005];
struct tree {
    int to, val, nxt;
} tree[300005];
inline void add (int x, int y, int z) {
    tree[++cnt].to = y;
    tree[cnt].val = z;
    tree[cnt].nxt = head[x];
    head[x] = cnt;
}
inline int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
bool cmp (node x, node y) {
    return x.z < y.z;
}
void dfs (int u, int fa) {
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for(int i = 0; i <= 20; i++) {
        f[u][i + 1] = f[f[u][i]][i];
        w1[u][i + 1] = max(w1[u][i], w1[f[u][i]][i]);
        w2[u][i + 1] = max(w2[u][i], w2[f[u][i]][i]);
        if(w1[u][i] != w1[f[u][i]][i]) {
            w2[u][i + 1] = max(w2[u][i + 1], min(w1[u][i], w1[f[u][i]][i]));
        }
    }
    for(int i = head[u]; i; i = tree[i].nxt) {
        if(tree[i].to == fa) continue;
        w1[tree[i].to][0] = tree[i].val;
        w2[tree[i].to][0] = -1e9;
        dfs(tree[i].to, u);
    }
}
inline int LCA (int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; i--) {
        if (dep[u] - (1 << i) >= dep[v]) {
            u = f[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = 20; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}
int query(int x, int y, int w) {
    int res = -1e9;
    for(int i = 20; i >= 0; i--) {
        if(dep[f[x][i]] >= dep[y]) {
            if(w1[x][i] < w) {
                res = max(res, w1[x][i]);
            } else {
                res = max(res, w2[x][i]);
            }
            x = f[x][i];
        }
    }
    return res;
}
int main () {
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf ("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);
    }
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    sort(edge + 1, edge + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        int fx = find (edge[i].x), fy = find (edge[i].y);
        if (fx != fy) {
            fa[fy] = fx;
            add (edge[i].x, edge[i].y, edge[i].z);
            add (edge[i].y, edge[i].x, edge[i].z);
            ans += edge[i].z;
            sum++;
            vis[i] = 1; 
            if (sum == n - 1) break;
        }
    }
    for(int i = 0; i <= 20; i++) {
        w1[1][i] = w2[1][i] = -1e9;
    }
    dfs (1, 0);
    mi = 2e9;
    for(int i = 1; i <= m; i++) {
        if(vis[i] == 0) {
            int w = edge[i].z;
            int lca = LCA(edge[i].x, edge[i].y);
            int maxu = query(edge[i].x, lca, w);
            int maxv = query(edge[i].y, lca, w);
            int tp = max(maxu, maxv);
            if(tp != -1e9) { 
                mi = min(mi, ans - tp + w);
            }
        }
    }
    printf ("%d", mi);
    return 0;
}