定义
次小生成树，就是边权之和次小的一棵生成树。有严格次小生成树与非严格次小生成树之分。
非严格次小生成树，它要满足 \(\Sigma_{w_{\text{次}}} \ge \Sigma_{w_{\text{最}}}\) ，也就是说非严格的可以和最小生成树权值相等；
严格次小生成树，它要满足 \(\Sigma_{w_{\text{次}}} > \Sigma_{w_{\text{最}}}\) ，也就是说严格的必须大于最小生成树的权值。
如何求次小生成树
非严格
首先我们要知道一个结论：次小生成树和最小生成树之间只有一条边的差异。
为什么要去掉最小生成树上的一条边呢？因为次小生成树和最小生成树必然至少有一条边不是共有的。为什么不去掉不在最小生成树上的边呢？因为这样最小生成树是没有变化的。
所以求出（非）严格次小生成树的朴素算法为：先建立一棵最小生成树。再枚举每一条不在最小生成树上的边，加入进去。再把生成树上最大的那条边删去即可，最后 \(O(m)\) 枚举完取一个 \(\min\) 就是答案。
如图
我们如果加入这个虚线的边，我们就需要从 \(1,2,3\) 中删掉一个权值最大的边，这样我们就得出了有这个虚边在的情况下的最小生成树了。
为什么不删 \(4,5\) 两条边，因为删了之后这就不是一棵树了。由此我们可以知道，当我们加入一条边 \((u,v)\) 时，我们只能删去 \((u,lca),(v,lca)\) 中最大的边。因此需要求最近公共祖先。
这样的时间复杂度是 \(O(nmlogm)\) 的，时间复杂度太大。怎么优化呢？
我们可以倍增维护，也可以树剖/\(\text{LCT}\) 进行维护，我选的倍增。这样就可以把时间复杂度优化成 \(O(mlognlogm)\) 的了。
严格
我们考虑，如果这个虚边的权值等于 \(\max\{1,2,3\}\) 的权值，那么我们求出来的这个生成树就不满足严格次小生成树的条件了。
为了解决这个问题，我们在倍增处理最大值的时候，同时也要处理一个严格的次大值，这样，当最大值权值和那个边相等的时候，我们就要用我们的次大值来更新了。
代码(严格)
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e5 + 5;
const int M = 3e5 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
struct node{
int u,v,w,next;
}edge[M<<1],Edge[M<<1]; int head[N],Head[N],num_edge,Num_edge;
vector <node> g[N];
int n,m,u,v,w,cnt,ans,tot;
int dep[N],f[N],fa[N][19],Max[N][19],Mex[N][19];
bool in_edge[M<<1];
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il void add(int from,int to,int dis)
{
edge[++num_edge] = (node){from,to,dis};
head[from] = num_edge;
}
il int find(int x) { return f[x] = f[x] == x ? x : find(f[x]); }
il bool cmp(node a,node b) { return a.w < b.w; }
il void Kruskal()
{
sort(edge+1,edge+num_edge+1,cmp);
for(re int i=1;i<=num_edge;i++)
{
u = edge[i].u , v = edge[i].v , w = edge[i].w;
int fx = find(u) , fy = find(v);
if(fx == fy) continue;
f[fy] = fx , tot += w;
in_edge[i] = 1;
g[u].push_back((node){u,v,w,0});
g[v].push_back((node){v,u,w,0});
++cnt;
if(cnt == n-1) break;
}
}
il void dfs(int x,int fath)
{
dep[x] = dep[fath] + 1 , fa[x][0] = fath;
for(re int i=0;i<(int)g[x].size();i++)
{
int y = g[x][i].v , w = g[x][i].w;
if(y == fath) continue;
Max[y][0] = w;
dfs(y,x);
}
}
il void init()
{
int mid;
for(re int j=1;j<=18;j++)
for(re int i=1;i<=n;i++)
{
mid = fa[i][j-1];
fa[i][j] = fa[mid][j-1];
Max[i][j] = max(Max[i][j-1],Max[mid][j-1]);
Mex[i][j] = max(Mex[i][j-1],Mex[mid][j-1]);
if(Max[i][j-1] != Max[mid][j-1]) Mex[i][j] = max(Mex[i][j],min(Max[i][j-1],Max[mid][j-1]));
}
}
il int LCA(int x,int y)
{
if(dep[x] < dep[y]) swap(x,y);
for(re int i=18;i>=0;i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if(x == y) return x;
for(re int i=18;i>=0;i--)
{
if(fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
il int strict_max(int x,int lca,int val)
{
int ans = 0;
for(re int i=18;i>=0;i--)
if(dep[fa[x][i]] >= dep[lca])
{
if(val == Max[x][i]) ans = max(ans,Mex[x][i]);
else ans = max(ans,Max[x][i]);
x = fa[x][i];
}
return ans;
}
il void get_ans()
{
ans = 1e15 + 5;
int lca,lmax,rmax;
for(re int i=1;i<=num_edge;i++)
{
if(in_edge[i]) continue;
u = edge[i].u , v = edge[i].v , w = edge[i].w;
lca = LCA(u,v);
lmax = strict_max(u,lca,w) , rmax = strict_max(v,lca,w);
//cout << lmax << " " << rmax << endl;
if(max(lmax,rmax) != w) ans = min(ans,tot + w - max(lmax,rmax));
}
//cout << tot;
cout << ans;
}
signed main()
{
n = read() , m = read();
for(re int i=1;i<=n;i++) f[i] = i;
for(re int i=1;i<=m;i++)
{
u = read() , v = read() , w = read();
if(u == v) continue;
add(u,v,w);
}
Kruskal();
dfs(1,0);
init();
get_ans();
return 0;
}
后言
这个玩意几乎也用不上，一天时间我学了俩没用的东西/cf