这道题做法还是比较容易想到的，就是码量有点大。
不严格次小生成树的思路就是先得到最小生成树，然后枚举每一条不在树里的边，找到所构成的环上权值最大的边替换掉。
而这道题要求严格次小，那么权值最大的边就不能与枚举的边权值相同，如果相同就替换环上次大的边即可。
我还是敲了树剖，对于最大和次大边我用pair来存，可能是STL的缘故不开O2只有90。在合并（线段树合并和lca两侧合并）时对最大和次大的处理如下：
inline pr get_max(pr x,pr y)
{
pr ans=mp(0,0);
if (x.first==y.first)
{
ans.first=x.first;
ans.second=max(x.second,y.second);
}
else
{
ans.first=max(x.first,y.first);
ans.second=max(max(x.second,y.second),min(x.first,y.first));
}
return ans;
}思路就是如果最大值相同那么次大值就从两个次大值里面选；否则最大值取两个最大值里面最大，次大值从剩下三个里面选最大。
需要注意的是要开long long，还有答案可能超过 $10^{9}$ ，所以inf取 $1e9$ 是不够的。还有要开O2
#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define mp make_pair
using namespace std;
inline ll read()
{
char ch=getchar();
ll f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct Edge{
ll next,to,w;
} edge[200005];
struct Edge2{
ll st,ed,w;
} edge2[300005];
struct Tree{
ll left,right;
pr mx;
} tree[400005];
bool intree[300005];
ll n,m,a,b,c,cnt,dfsord,head[100005],fa[100005],son[100005],top[100005],siz[100005],deep[100005],id[100005],w[100005],wnew[100005],fath[100005];
inline void add(ll u,ll v,ll w)
{
edge[++cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
inline pr get_max(pr x,pr y)
{
pr ans=mp(0,0);
if (x.first==y.first)
{
ans.first=x.first;
ans.second=max(x.second,y.second);
}
else
{
ans.first=max(x.first,y.first);
ans.second=max(max(x.second,y.second),min(x.first,y.first));
}
return ans;
}
inline void pushup(ll x) { tree[x].mx=get_max(tree[x*2].mx,tree[x*2+1].mx); }
void build(ll x,ll l,ll r)
{
tree[x].left=l;
tree[x].right=r;
if (r-l==1) tree[x].mx.first=wnew[l];
else
{
ll mid=(l+r)>>1;
build(x*2,l,mid);
build(x*2+1,mid,r);
pushup(x);
}
}
pr query(ll x,ll l,ll r)
{
if (l<=tree[x].left && r>=tree[x].right) return tree[x].mx;
else
{
pr ans=mp(0,0);
ll mid=(tree[x].left+tree[x].right)>>1;
if (l<mid) ans=query(x*2,l,r);
if (r>mid) ans=get_max(ans,query(x*2+1,l,r));
return ans;
}
}
void dfs1(ll x,ll f,ll dep)
{
fa[x]=f;
deep[x]=dep;
siz[x]=1;
ll mx=0;
for (ll i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to;
if (y==f) continue;
w[y]=edge[i].w;
dfs1(y,x,dep+1);
siz[x]+=siz[y];
if (siz[y]>mx)
{
mx=siz[y];
son[x]=y;
}
}
}
void dfs2(ll x,ll topf)
{
top[x]=topf;
id[x]=++dfsord;
wnew[dfsord]=w[x];
if (!son[x]) return;
dfs2(son[x],topf);
for (ll i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to;
if (y==fa[x] || y==son[x]) continue;
dfs2(y,y);
}
}
inline ll qRange(ll u,ll v,ll mx) // = ? mx2 : mx
{
pr ans=mp(0,0);
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
ans=get_max(ans,query(1,id[top[u]],id[u]+1));
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
if (id[u]!=id[v]) ans=get_max(ans,query(1,id[u]+1,id[v]+1));
return (ans.first==mx) ? ans.second : ans.first;
}
inline void init() { for (ll i=1;i<=n;i++) fath[i]=i; }
ll getfa(ll x) { return (x==fath[x]) ? x : fath[x]=getfa(fath[x]); }
inline bool merge(ll x,ll y)
{
ll gfx=getfa(x),gfy=getfa(y);
if (gfx==gfy) return 0;
fath[gfx]=fath[gfy];
return 1;
}
inline bool cmp(Edge2 x,Edge2 y) { return x.w<y.w; }
int main()
{
n=read(); m=read();
init();
for (ll i=1;i<=m;i++) edge2[i].st=read(),edge2[i].ed=read(),edge2[i].w=read();
sort(edge2+1,edge2+m+1,cmp);
ll ecnt=0,sum=0;
for (ll i=1;i<=m;i++)
{
ll x=edge2[i].st,y=edge2[i].ed,z=edge2[i].w;
if (!merge(x,y)) continue;
add(x,y,z);
add(y,x,z);
intree[i]=1;
ecnt++;
sum+=z;
if (ecnt==n-1) break;
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n+1);
ll ans=1e18;
for (ll i=1;i<=m;i++)
{
if (intree[i]) continue;
ans=min(ans,sum-qRange(edge2[i].st,edge2[i].ed,edge2[i].w)+edge2[i].w);
}
printf("%lld",ans);
return 0;
}