题主的做法是 Kruskal 后 LCA直接求, 三个倍增数组

题主这里的问题如下:

lca内倍增数组的更改顺序应该是

1. 第二大 2. 第一大 3. LCA

同时, 如果没有记录第二大需要记录 这种情况同样是 WA#1 #4 #10

其次注意Update(调整第二大倍增/LCA)的时候, 请注意当两个第一大相等的时候, 需要特殊判定

根据 @风流瀑布 , 还有可能是LCA和Kruskal中出现了问题 https://www.luogu.com.cn/discuss/show/153473

其次如果#9 #10 RE, 数组开的过小

如果#10 WA, 无限大开的不够大

如果用的是其他算法, 注意#10有自环 几乎全部点都有重边 但是在题主使用的这个算法中不需要做调整

重边和自环的处理方式可以参考题主的代码

重边和自环应该也可以用visited数组解决

如果TLE 请使用更快速的读入和输出, 请使用register 和 inline 来提速 LCA内使用预处理的log

AC代码 可以参考题主的代码, 简单易读 请勿照抄 调试了很久

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<map>
using namespace std;

struct record {
    int u,v,w;
};
struct edge {
    int to,w;
};
bool comp (record a, record b) {
    return a.w<b.w;
}
int n,m;
vector<edge> edges[1000005];
record pre[1000005];
int f[1000005];
bool inKruskal[1000005], visited[1000005];
long long kruskalSize;
long long ans = __LONG_LONG_MAX__;
int Log[1000005], depth[1000005];
int fa[1000005][21], maxi[1000005][21];
int maxj[1000005][21];

inline int update (int a1, int a2, int b1, int b2) {
    int maxNum = max(a1,b1);
    int res;
    if (a1==b1) {
        res = max(a2,b2);
    }
    else if (maxNum==a1) {
        res = max(a2,b2);
        res = max(res,b1);
    }
    else if (maxNum==b1) {
        res = max(a2,b2);
        res = max(res,a1);
    }
    return res;
}
inline int lca (int x, int y, int cur) {
    int maxSec = 0;
    int ans = 0;
    if (depth[x]>depth[y]) {
       swap(x,y);
    }
    for (int i=17;i>=0;i--) {
       if (depth[fa[y][i]]>=depth[x]) {
            maxSec = update(ans,maxSec,maxi[y][i],maxj[y][i]);
            ans = max(ans,maxi[y][i]);
            y=fa[y][i];
        }
    }
    if (x==y) {
        if (ans == cur) return maxSec;
        else return ans;
    }
    for (int k=17;k>=0;k--) {
        if (fa[x][k]!=fa[y][k]) {
            maxSec = update(ans,maxSec,maxi[y][k],maxj[y][k]);
            ans = max(maxi[y][k],ans);
            maxSec = update(ans,maxSec,maxi[x][k],maxj[x][k]);
            ans = max(maxi[x][k],ans);
            x=fa[x][k];
            y=fa[y][k];
        }
    }             
    maxSec = update(ans,maxSec,maxi[y][0],maxj[y][0]);
    ans = max(ans,maxi[y][0]);
    maxSec = update(ans,maxSec,maxi[x][0],maxj[x][0]);
    ans = max(ans,maxi[x][0]);
    if (ans == cur) return maxSec;
    return ans;
}
inline void dfs(int current) {
    for (int i=0;i<edges[current].size();i++) {
        edge npos = edges[current][i];
        if (visited[npos.to]) continue;
        depth[npos.to]=depth[current]+1;
        fa[npos.to][0]=current;
        maxi[npos.to][0]=npos.w;
        visited[npos.to]=true;
        dfs(npos.to);
    }
}

inline int find (int x) {
    if (f[x]==x) return x;
    f[x] = find(f[x]);
    return f[x];
}
inline void kruskal () {
    int cnt = 0;
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=m;i++) {
        int nx = find(pre[i].u);
        int ny = find(pre[i].v);
        if (f[nx]!=f[ny]) {
            kruskalSize += pre[i].w;
            inKruskal[i] = true;
            f[nx]=f[ny];
            cnt++;
            edges[pre[i].u].push_back({pre[i].v,pre[i].w});
            edges[pre[i].v].push_back({pre[i].u,pre[i].w});
            if (cnt==n-1) break;
        }
    }
}
inline void prepare () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main () {
    map<int,bool> error[100005];
    map<int,int> least[100005];
    map<int,int> pos[100005];
    prepare();
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        // if (u==v) {
        //     i--;
        //     m--;
        //     cout<<"QERROR:"<<u<<" "<<v<<" "<<w<<endl;
        //     continue;
        // }
        // if (error[u][v]) {
        //     least[u][v] = min(least[u][v],w);
        //     least[v][u] = min(least[v][u],w);
        //     pre[pos[u][v]].w = least[u][v];
        //     i--;
        //     m--;
        //     continue;
        // }
        // error[u][v] = true;
        // error[v][u] = true;
        // pos[u][v] = i;
        // pos[v][u] = i;
        // least[u][v] = w;
        // least[v][u] = w;
        pre[i]={u,v,w};
    }
    sort(pre+1,pre+1+m,comp);
    kruskal();
    fa[1][0] = 0;
    depth[1] = 1;
    visited[1] = true;
    dfs(1);
    for(int i=1;i<=17;i++) {
        for(int j=1;j<=n;j++){
            fa[j][i] = fa[fa[j][i-1]][i-1]; 
            maxi[j][i] = max(maxi[j][i-1],maxi[fa[j][i-1]][i-1]);
            maxj[j][i] = max(maxj[j][i-1],maxj[fa[j][i-1]][i-1]);
            if (maxi[j][i-1]==maxi[fa[j][i-1]][i-1]) continue;
            maxj[j][i] = max(maxj[j][i],min(maxi[j][i-1],maxi[fa[j][i-1]][i-1]));
        }
    }
    for (int i=1;i<=m;i++) {
        if (!inKruskal[i]) {
            int desc = lca(pre[i].u,pre[i].v,pre[i].w);
            long long current = kruskalSize-desc+pre[i].w;
            if (current>kruskalSize) ans = min(ans,current);
        }
    }
    cout<<ans<<endl;
}

总结一下: 任何错误都有可能导致#1 #4 出问题, 请仔细调试代码, #10请注意自环