次小生成树学习笔记（已完成）
2026-05-14 20:57:06
发布于：上海
前置知识点：倍增lca 树上倍增 最小为生成树
如果你对此并不了解，请移步：
1.倍增lca短篇讲解
（这篇帖子是我专门为了次小生成树写的，所以可能会合适一点）
2.最小生成树一篇通（未完成）
（虽然没有完成，但也只是某一道例题没有弄完。基础的东西都已经弄好了。）
——————————————————————————————————————————
然后就可以开始我们的旅行了。
（先说做法。不过这个做法是我从洛谷书上学的会相似。后面就全部都是我自己的思考）
首先，它的名字叫次小生成树。所以自然而然，我们会去思考它和最小生成树之间是否有关系。
其次，它是严格次小生成树。是排第二的，所以我们可以进行一些猜测。比如：它是否是在最小生成树的基础上进行修改而成的。（比如：对几条边进行替换）
不过事实上，我们可以证明：次小生成树是在最小生成树上的基础上替换一条边建成的。
以下是证明过程：
采用反证法。我们可以假设某颗”严格次小生成树“与最小生成树有k()条。断开这些边，发现原树被分成了个连通块。选择其中的个，并用最小生成树的边将它们变成一个连通块。再将最后一个点和这个连通块用次小生成树的边连在一起。
发现此时，这颗新的树的边权之和小于”严格次小生成树“。
以此我们证明出：次小生成树是在最小生成树上的基础上替换一条边建成的。
大致的做法应该也差不多出来了。
我们先处理出最小生成树。枚举每一条不在最小生成树中的边，将它们依次加入最小生成树。此时，最小生成树中会形成一个环。我们在环中（寻找除了这条加入的边）其它边中边权最大的边，然后把它去掉。算树的边权之和。
这样算完后，最小的那个数就是次小生成树。
值得一提的是，如果这个环中最后筛选出来的边的边权与新加入的这条边的边权相等，那么就去找次大。（注意有可能存在次大值=最大值的情况，即不存在次小生成树）（不过这条边没有不代表其他便没有）
注意到如果是普通枚举的话会超时。用在树中比较常见的优化技巧：树上倍增。
用树上倍增预处理出每一个点往上走个点的路径中边权最大和次大。
适合用kruskal。
接下来就是代码分析环节：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n,m,now;
struct Node{
int x,y;
int z;
}node[N];
struct Node1{
int z,q;
};
vector<Node1>v[N];
int c[N];
bool if1[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
int ff(int x){
return (x==c[x])?x:c[x]=ff(c[x]);
}
ll ans1;//最小生成树
void kruskal(){
sort(node+1,node+1+now,cmp);
for(int i=1;i<=now;i++){
int p=ff(node[i].x),q=ff(node[i].y);
if(p==q)continue;
ans1+=node[i].z;
c[p]=q;
v[node[i].x].push_back({node[i].y,node[i].z});
v[node[i].y].push_back({node[i].x,node[i].z});
if1[i]=1;
}
return;
}
int deep[N];//每个点所在的深度
int f[N][20];//第i个点向上走2^i个位置到达的点
int mx[N][20];//第i个点向上走2^i个位置的边权最大值
int mx2[N][20];//边权次大值
void dfs(int x){
deep[x]=deep[f[x][0]]+1;
for(int i=1;i<=18;i++){
f[x][i]=f[f[x][i-1]][i-1];
if(mx[f[x][i-1]][i-1]>mx[x][i-1]){
mx2[x][i]=max(mx[x][i-1],mx2[f[x][i-1]][i-1]);
mx[x][i]=mx[f[x][i-1]][i-1];
}
if(mx[x][i-1]>mx[f[x][i-1]][i-1]){
mx2[x][i]=max(mx2[x][i-1],mx[f[x][i-1]][i-1]);
mx[x][i]=mx[x][i-1];
}
if(mx[x][i-1]==mx[f[x][i-1]][i-1]){
mx2[x][i]=max(mx2[x][i-1],mx2[f[x][i-1]][i-1]);
mx[x][i]=mx[x][i-1];
}
}
for(int i=0;i<v[x].size();i++){
int to=v[x][i].z;
int len=v[x][i].q;
if(to==f[x][0])continue;
f[to][0]=x,mx[to][0]=len;
dfs(to);
}
}
int lca(int u,int v){
if(deep[u]<deep[v])swap(u,v);
for(int i=18;i>=0;i--){
if(deep[u]-deep[v]>=(1<<i))u=f[u][i];
}
if(u==v)return u;
for(int i=18;i>=0;i--){
if(f[u][i]!=f[v][i]){
u=f[u][i];
v=f[v][i];
}
}
return f[u][0];
}
long long cal(int u,int v,int w){
int l=lca(u,v);
int nmx=0,nmx2=0;
for(int i=18;i>=0;i--){
if(deep[f[u][i]]>=deep[l]){
if(nmx==mx[u][i])nmx2=max(nmx2,mx2[u][i]);
if(nmx>mx[u][i])nmx2=max(mx[u][i],nmx2);
if(nmx<mx[u][i]){
nmx2=max(nmx,mx2[u][i]),nmx=mx[u][i];
}
u=f[u][i];
}
if(deep[f[v][i]]>=deep[l]){
if(nmx==mx[v][i])nmx2=max(nmx2,mx2[v][i]);
if(nmx>mx[v][i])nmx2=max(mx[v][i],nmx2);
if(nmx<mx[v][i]){
nmx2=max(nmx,mx2[v][i]),nmx=mx[v][i];
}
v=f[v][i];
}
}
if(w!=nmx)return ans1-nmx+w;
if(nmx2)return ans1-nmx2+w;
return LONG_LONG_MAX;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>node[++now].x>>node[now].y>>node[now].z;
if(node[now].x==node[now].y)now--;//处理自环
}
for(int i=1;i<=n;i++)c[i]=i;
kruskal();
dfs(1);//树上倍增初始化
ll ans=LONG_LONG_MAX;
for(int i=1;i<=now;i++){
if(!if1[i])ans=min(cal(node[i].x,node[i].y,node[i].z),ans);
}
cout<<ans;
return 0;
}
这个代码有点点复杂。不过大多都是重复和模板的拼凑。
我们一点点分析。
1.输入
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>node[++now].x>>node[now].y>>node[now].z;
if(node[now].x==node[now].y)now--;//处理自环
}
注意到需要处理自环。注意到普通的最小生成树不需要处理自环。
why。
因为自环的边肯定不会出现在最小生成树中。所以意味着后期遍历边会轮到它。
那么树中就没有环了，操作也进行不了。
开局把它请出去是比较明智的选择。
不过这个点有点刁钻了。如何想到?
1.被相似题目坑过一把
2.仔细读题
2.kruskal
void kruskal(){
sort(node+1,node+1+now,cmp);
for(int i=1;i<=now;i++){
int p=ff(node[i].x),q=ff(node[i].y);
if(p==q)continue;
ans1+=node[i].z;
c[p]=q;
v[node[i].x].push_back({node[i].y,node[i].z});
v[node[i].y].push_back({node[i].x,node[i].z});
if1[i]=1;
}
return;
}
额这个没什么好分析的。不过注意到有加边操作。
因为后期的倍增预处理是在最小生成树中去做的。所以需要提前把最小生成树建出来。
3.树上倍增初始化
void dfs(int x){
deep[x]=deep[f[x][0]]+1;
for(int i=1;i<=18;i++){
f[x][i]=f[f[x][i-1]][i-1];
if(mx[f[x][i-1]][i-1]>mx[x][i-1]){
mx2[x][i]=max(mx[x][i-1],mx2[f[x][i-1]][i-1]);
mx[x][i]=mx[f[x][i-1]][i-1];
}
if(mx[x][i-1]>mx[f[x][i-1]][i-1]){
mx2[x][i]=max(mx2[x][i-1],mx[f[x][i-1]][i-1]);
mx[x][i]=mx[x][i-1];
}
if(mx[x][i-1]==mx[f[x][i-1]][i-1]){
mx2[x][i]=max(mx2[x][i-1],mx2[f[x][i-1]][i-1]);
mx[x][i]=mx[x][i-1];
}
}
for(int i=0;i<v[x].size();i++){
int to=v[x][i].z;
int len=v[x][i].q;
if(to==f[x][0])continue;
f[to][0]=x,mx[to][0]=len;
dfs(to);
}
}
额。这个就有点麻烦了。
因为lca是前置知识点，所以这边我主要是想提对于最大值和次大值的预处理。
的定义是：在第个点到这个点往上个点的路径中边权最大者。
的定义是：在第个点到这个点往上个点的路径中边权次大者。
接下来我来分析一下判断：
if(mx[f[x][i-1]][i-1]>mx[x][i-1]){
mx[x][i]=mx[f[x][i-1]][i-1];
mx2[x][i]=max(mx[x][i-1],mx2[f[x][i-1]][i-1]);
}
if(mx[f[x][i-1]][i-1]>mx[x][i-1])
这个判断的意思是:如果点往上个点 到 点往上个点 的路径中（即红色路段）中的边权最大值 点到点往上个点的路径中（即绿色路段）中的边权最大值
mx[x][i]=mx[f[x][i-1]][i-1];
这句话的意思是：将点到点往上个点的路径中（即红色+绿色路段）中的边权最大值 赋值为 点往上个点 到 点往上个点 的路径中（即红色路段）中的边权最大值
mx2[x][i]=max(mx[x][i-1],mx2[f[x][i-1]][i-1]);
这句话的意思是什么我就不解释了。感觉前两行的解释过于冗长了。
我主要想解释一下原理。理论上而言，能够构成的应该只有红色段和绿色段的次大值。
但是由于绿色路段的最大值并不是（红+绿）路段的最大值。所以次大值就可以在绿色最大值和红色次大值之间选择。
后面两个大同小异。
4.寻找次大生成树
long long cal(int u,int v,int w){
int l=lca(u,v);
int nmx=0,nmx2=0;
for(int i=18;i>=0;i--){
if(deep[f[u][i]]>=deep[l]){
if(nmx==mx[u][i])nmx2=max(nmx2,mx2[u][i]);
if(nmx>mx[u][i])nmx2=max(mx[u][i],nmx2);
if(nmx<mx[u][i]){
nmx2=max(nmx,mx2[u][i]),nmx=mx[u][i];
}
u=f[u][i];
}
if(deep[f[v][i]]>=deep[l]){
if(nmx==mx[v][i])nmx2=max(nmx2,mx2[v][i]);
if(nmx>mx[v][i])nmx2=max(mx[v][i],nmx2);
if(nmx<mx[v][i]){
nmx2=max(nmx,mx2[v][i]),nmx=mx[v][i];
}
v=f[v][i];
}
}
if(w!=nmx)return ans1-nmx+w;
if(nmx2)return ans1-nmx2+w;
return LONG_LONG_MAX;
}
int l=lca(u,v);
我们找l的目的是在以它为最小深度点的环中去寻找边权最大值和次大值。
后面for循环中的内容和刚刚分析的判断本质相同，所以我要偷懒。
不过要注意的是，最后的结果需要用 long long存储。
好了。差不多分析完了。下一篇学习笔记见。
这里空空如也
有帮助，赞一个