记录编号	605436	评测结果	AAAAAAAAAA
题目名称	2453.次小生成树	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.347 s
提交时间	2025-09-01 11:13:51	内存使用	11.00 MiB

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

const int N = 1000001, M = 600001, INF = 1e9 + 7;

struct st {
    int x, y, z;
} kr[M];

int n, m, k, rt, cnt, q, ans = INF, anz;
int nxt[M << 1], last[N], a[M << 1], w[M << 1];
int fa[N], f[N][21], dep[N], sz[N], an[N][21], an1[N][21];
bool l[N];

void add(int x, int y, int z) {
    nxt[++k] = last[x];
    last[x] = k;
    a[k] = y;
    w[k] = z;
}

bool cmp(st a, st b) {
    return a.z < b.z;
}

int find(int x) {
    if (x == fa[x]) return x;
    else return fa[x] = find(fa[x]);
}

void kruskal() {
    sort(kr + 1, kr + 1 + m, cmp);
    for (int i = 1; i <= m; i++) {
        if (kr[i].x == kr[i-1].x && kr[i].y == kr[i-1].y) {
            l[i] = 1;
            continue;
        }
        int b = find(kr[i].x), c = find(kr[i].y);
        if (b != c) {
            fa[b] = c;
            cnt++;
            l[i] = 1;
            anz += kr[i].z;
            add(kr[i].x, kr[i].y, kr[i].z);
            add(kr[i].y, kr[i].x, kr[i].z);
        }
        if (cnt == n - 1) return;
    }
}

void dfs_lca(int x, int fa, int y) {
    dep[x] = dep[fa] + 1;
    f[x][0] = fa;
    an[x][0] = y;
    an1[x][0] = 0;
    for (int i = 1; (1 << i) <= dep[x]; i++) {
        f[x][i] = f[f[x][i-1]][i-1];
        an[x][i] = max(an[f[x][i-1]][i-1], an[x][i-1]);
        an1[x][i] = max(
            max(an1[f[x][i-1]][i-1], an1[x][i-1]),
            an[x][i-1] == an[f[x][i-1]][i-1] ? 0 : min(an[x][i-1], an[f[x][i-1]][i-1])
        );
    }
    for (int i = last[x]; i; i = nxt[i])
        if (a[i] != fa)
            dfs_lca(a[i], x, w[i]);
}

int lca(int x, int y, int z) {
    if (dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y], ans = 0;
    for (int i = 0; (1 << i) <= d; i++)
        if ((1 << i) & d) {
            ans = max(ans, (an[x][i] == z ? an1[x][i] : an[x][i]));
            x = f[x][i];
        }
    if (x == y) return ans;
    for (int i = log2(dep[x]); i >= 0; i--)
        if (f[x][i] != f[y][i]) {
            ans = max(
                (max(an[x][i], an[y][i]) == z ? an1[x][i] : max(an[x][i], an[y][i])),
                ans
            );
            x = f[x][i];
            y = f[y][i];
        }
    return max(
        (max(an[x][0], an[y][0]) == z ? max(max(an1[x][0], an1[y][0]), ans) : max(an[x][0], an[y][0])),
        ans
    );
}

signed main() {
	freopen("secmst.in","r",stdin);
	freopen("secmst.out","w",stdout); 
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &kr[i].x, &kr[i].y, &kr[i].z);
    kruskal();
    for (int i = 1; i <= n; i++)
        if (!dep[i])
            dfs_lca(i, 0, 0);
    for (int x, i = 1; i <= m; i++)
        if (!l[i]) {
            x = lca(kr[i].x, kr[i].y, kr[i].z);
            if (kr[i].z - x) ans = min(ans, kr[i].z - x);
        }
    printf("%d", ans + anz);
    return 0;
}