构建完MST后，枚举非树边(u,v,w)，在树上u->v的路径中找一条权值最大的边(权为maxn)，替换掉它

这样在 w=maxn 时显然不能满足严格次小。但是这个w可以替换掉树上严格小于maxn的次大边

用倍增维护MST上路径的最大值、次大值，每条非树边的查询复杂度就为O(logn)

ps:1.倍增更新次大值时，未必是从最大值转移，要先赋值较大的次大值，再与较小的那个最大值比较。

2.maxn!=w时，是可以从maxn更新的(不能更新就是上面情况啊)

倍增处理部分我还是在dfs里写吧 md改了一晚上

//648ms 31.61MB#include 
      
       #include 
       
        #include 
        
          //#define gc() getchar() #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=1e5+5,M=3e5+5,D=18,MAXIN=2e6; int n,m,F[N],Enum,H[N],to[N<<1],nxt[N<<1],val[N<<1],dep[N],fa[N][D],maxn[N][D],s_maxn[N][D]; bool ist[M]; char IN[MAXIN],*SS=IN,*TT=IN; struct Edge { int fr,to,val; bool operator <(const Edge &a)const{ return val
         
          maxn[x][i-1]) s_maxn[x][i]=std::max(s_maxn[x][i],maxn[x][i-1]); else if(maxn[fa[x][i-1]][i-1]
          
           maxn[x][i-1]) // s_maxn[x][i]=std::max(s_maxn[x][i],maxn[x][i-1]); // else if(maxn[fa[x][i-1]][i-1]
           
            =0; --i) if(dep[fa[u][i]]>=dep[lca]) { if(maxn[u][i]!=w) res=std::max(res,maxn[u][i]); else res=std::max(res,s_maxn[u][i]); u=fa[u][i]; } return res; } int LCA(int u,int v) { if(dep[u]
            
             =0; --i) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i]; // if(t&(1<
             
              =0; --i) if(fa[u][i]!=fa[v][i]) u=fa[u][i], v=fa[v][i]; return fa[u][0]; } int main() { n=read(),m=read(); for(int i=1; i<=m; ++i) e[i].fr=read(),e[i].to=read(),e[i].val=read(); LL tot=Kruskal(),res=e[m].val+tot; dep[1]=1, pre_DFS(1);//, Init(); for(int u,v,w,lmax,rmax,i=1; i<=m; ++i) if(!ist[i]) { u=e[i].fr, v=e[i].to, w=LCA(u,v); lmax=Query(u,w,e[i].val), rmax=Query(v,w,e[i].val); res=std::min(res,tot+e[i].val-std::max(lmax,rmax)); } printf("%lld",res); return 0; }