涉及知识点：最小生成树，倍增
题意
题目写的很清楚，给定一张N个点M条边的无向图，求无向图的严格次小生成树。
设最小生成树的边权之和为sum，严格次小生成树就是指边权之和大于sum的生成树中最小的一个
拓展：
边权和最小的满足边权和大于等于最小生成树边权和的生成树为非严格次小生成树
边权和最小的满足边权和严格大于最小生成树边权和的生成树为严格次小生成树
其实次小生成树算是一道板子题，所以一定要学好解这种题的思路和做法
思路
引理
我们可以很容易发现，由于最小生成树是一棵树，而对于一颗树只要断掉任意一条边，这颗树就会变为两个连通分量，但如果我们又在这两个连通分量各找一个点相连，又会变成一颗新的树
尝试
我们设上述被断掉的边为\((u,v)\)，而新连的边为\((x,y)\)，原最小生成树的边权和为\(sum\)，那么新的树的边权和就为\((sum-dis_{u,v}+dis_{x,y})\)，而此时相当于整体边权和减少了\((dis_{u,v}-dis_{x,y})\)（这是个负数），也就是增大了\((dis_{x,y}-dis_{u,v})\)（注意变号，前后顺序换了）
这给我们一个启示，为何不对于每条不在MST上的边，我们都尝试去更新边权和？
做法
因此我们只需要这么做：
第一步
对于每条不在MST上的边\((u,v)\)，找到\(u\)到\(v\)在MST中的路径中最长和次长的边
为什么？要点与解释如下
- 为什么要找长的边？ 因为当\(dis_{x,y}\)确定时，\(dis_{u,v}\)越大，增大的值就越小，增大的值最小的时候就产生了次小生成树
- 为什么要找\(u\)到\(v\)在MST中的路径？ 我们假设要切断的边不在\(u\)到\(v\)在树上的路径上，这时候如果连接\((u,v)\)，就会出现一条环，别说次小生成树了，连树都不是
- 为什么还要找次长边？ 万一最长边和\(dis_{u,v}\)一样长，这样生成的就是非严格次小生成树了，因此此处的次长边也是严格次长
第二步
设最长边为\(max_1\)，次长边为\(max_2\)，MST的边权和为\(sum\)
-
若\(dis_{u,v}>max_1\)，将边最长边替换为\((u,v)\)，记录下新边权和\(sum-max_1+dis_{u,v}\)
-
若\(dis_{u,v}=max_1\)，将边次长边替换为\((u,v)\)，记录下新边权和\(sum-max_2+dis_{u,v}\)
-
若\(dis_{u,v}<max_1\)，这是不可能出现的事，不然\((u,v)\)就会在MST中
第三步
直接输出记录下的新边权和的最小值
优化
本题需要用树上倍增法优化快速求\(u\)到\(v\)最长和次长的边
老规矩，\(fa[x][i]\)表示\(x\)的\(2^i\)个祖先，\(pa[x][i][0]\)表示\(x\)到\(x\)的\(2^i\)祖先的最大值，\(pa[x][i][1]\)表示\(x\)到\(x\)的\(2^i\)祖先的次大值
初始值：
\[fa[x][0]=father(x) \\ pa[x][i][0]=dis(x,father(x)) \\ pa[x][i][1]=0 \]递推式：
\[fa[x][i]=fa[fa[x][i-1]][i-1] \\ pa[x][i][0]=max(pa[x][i-1][0],pa[fa[x][i-1]][i-1][0]) \\ pa[x][i][1]=\begin{cases} max(pa[x][i-1][0],pa[fa[x][i-1]][i-1][1]),pa[x][i-1][0]<pa[fa[x][i-1]][i-1][0] \\ max(pa[x][i-1][1],pa[fa[x][i-1]][i-1][1]),pa[x][i-1][0]=pa[fa[x][i-1]][i-1][0] \\ max(pa[x][i-1][1],pa[fa[x][i-1]][i-1][0]),pa[x][i-1][0]>pa[fa[x][i-1]][i-1][0] \end{cases} \]代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int MAXN=1e5+5,MAXM=3e5+5,MAXBIN=18;
int n,m;
LL sum=0,ans=LONG_LONG_MAX;
vector<pii>g[MAXN];
class UFS{
private:
int fa[MAXN];
public:
inline void init(){
for(int i=1;i<=n;i++) fa[i]=i;
}
inline int get(int x){
if(fa[x]==x) return x;
else return fa[x]=get(fa[x]);
}
inline void merge(int x,int y){
fa[y]=x;
}
}ufs;
struct EDGE{
int u,v,w;
bool operator<(EDGE y){
return w<y.w;
}
}e[MAXM];
queue<EDGE>nonmst;
void kruskal(){
ufs.init();
sort(e+1,e+1+m);
for(int i=1;i<=m;i++){
int x=ufs.get(e[i].u),y=ufs.get(e[i].v);
if(x!=y){
ufs.merge(x,y);
sum+=e[i].w;
g[e[i].u].emplace_back(e[i].v,e[i].w);
g[e[i].v].emplace_back(e[i].u,e[i].w);
}
else nonmst.push(e[i]);
}
}
int fa[MAXN][MAXBIN],pa[MAXN][MAXBIN][2],dep[MAXN];
void dfs(int x,int fno,int dis){
dep[x]=dep[fno]+1;
fa[x][0]=fno;
pa[x][0][0]=dis;
pa[x][0][1]=0;
for(int i=1;i<MAXBIN;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
pa[x][i][0]=max(pa[x][i-1][0],pa[fa[x][i-1]][i-1][0]);
if(pa[x][i-1][0]<pa[fa[x][i-1]][i-1][0]) pa[x][i][1]=max(pa[x][i-1][0],pa[fa[x][i-1]][i-1][1]);
else if(pa[x][i-1][0]==pa[fa[x][i-1]][i-1][0]) pa[x][i][1]=max(pa[x][i-1][1],pa[fa[x][i-1]][i-1][1]);
else pa[x][i][1]=max(pa[x][i-1][1],pa[fa[x][i-1]][i-1][0]);
}
for(auto it:g[x]){
if(it.first!=fno) dfs(it.first,x,it.second);
}
}
pii get(int x,int y){
int max1=0,max2=0;
if(dep[x]>dep[y]) swap(x,y);
int delt=dep[y]-dep[x];
for(int i=0;delt;i++,delt>>=1){
if(delt&1){
if(pa[y][i][0]>max1){
max2=max1;
max1=pa[y][i][0];
if(pa[y][i][1]>max2){
max2=pa[y][i][1];
}
}
else{
max2=max(max2,pa[y][i][0]);
}
y=fa[y][i];
}
}
if(x==y) return make_pair(max1,max2);
for(int i=MAXBIN-1;i>=0 && x!=y;i--){
if(fa[x][i]!=fa[y][i]){
max1=max({max1,pa[x][i][0],pa[y][i][0]});
if(pa[x][i][0]<pa[y][i][0]) max2=max({max2,pa[x][i][0],pa[y][i][1]});
else if(pa[x][i][0]==pa[y][i][0]) max2=max({max2,pa[x][i][1],pa[y][i][1]});
else max2=max({max2,pa[x][i][1],pa[y][i][0]});
x=fa[x][i];y=fa[y][i];
}
}
if(max1<max(pa[x][0][0],pa[y][0][0])){
max1=max(pa[x][0][0],pa[y][0][0]);
if(pa[x][0][0]<pa[y][0][0]) max2=max({max2,pa[x][0][0],pa[y][0][1]});
else if(pa[x][0][0]==pa[y][0][0]) max2=max({max2,pa[x][0][1],pa[y][0][1]});
else max2=max({max2,pa[x][0][1],pa[y][0][0]});
}
else max2=max({max2,pa[x][0][0],pa[y][0][0]});
return make_pair(max1,max2);
}
int main(){
cin>>n>>m;
for(int i=1,x,y,z;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
kruskal();
dep[0]=0;
dfs(1,0,0);
// for(int i=1;i<=n;i++){
// cout<<i<<": ";
// for(int j=0;j<MAXBIN;j++) cout<<pa[i][j][1]<<' ';
// cout<<endl;
// }
while(!nonmst.empty()){
EDGE cur=nonmst.front();nonmst.pop();
if(cur.u==cur.v) continue;
pii res=get(cur.u,cur.v);
// assert(res.first>res.second);
// cout<<ans<<endl;
// cout<<cur.u<<' '<<cur.v<<' '<<cur.w<<' '<<res.first<<' '<<res.second<<endl;
if(cur.w>res.first) ans=min(ans,sum-(LL)res.first+(LL)cur.w);
else if(cur.w==res.first) ans=min(ans,sum-(LL)res.second+(LL)cur.w);
}
cout<<ans<<endl;
return 0;
}