次小生成树

定义：边权之和大于最小生成树边权之和的生成树中最小的一个

思路：枚举所有未连接的边连上，那么一定会出现一个环，再去掉环上最大的边（如果与新加的边等大就要去次小边），这个最小值就为次小生成树的值

朴素求法：先用kruskal求出最小生成树，然后从每个点开始找到其他点的最大边与次大边，然后枚举所有边

复杂度\(O(n^2+m)\)

LAC优化：就是只讨论一棵树，对每个点记录向上跳\(2^i\)经过的最大边与次大边

注意LAC的i=0时的特殊处理

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
const int N = 1e5 + 10,M = 3e5 + 10;
int n,m,sum;

vector<PII> ed[N];//新图
struct edge{int u,v,len;
bool operator<(const edge &x)const{return len < x.len;}};
edge _ed[M];//旧图
int pre[N];//并查集
bool use[M];//边使用
void init(){for(int i = 1;i <= n;i++) pre[i] = i;}//并查集初始化
int find(int x){if(pre[x] == x) return pre[x];else return pre[x] = find(pre[x]);}
void kruskal(){
	init();
	sort(_ed + 1,_ed + 1 + m);
	for(int i = 1;i <= m;i++){
		if(find(_ed[i].u) != find(_ed[i].v)){
			use[i] = 1;
			sum += _ed[i].len;
			pre[find(_ed[i].u)] = find(_ed[i].v);
			ed[_ed[i].u].push_back({_ed[i].v,_ed[i].len});
			ed[_ed[i].v].push_back({_ed[i].u,_ed[i].len});
		}
	}
}

int dep[N],fa[N][21] = {0};
PII ma[N][21];
void bfs(){
	queue<int> qu;
	qu.push(1);
	dep[1] = 1;
	while(!qu.empty()){
		int u = qu.front();
		qu.pop();
		for(auto e:ed[u]){
			int v = e.fi,len = e.se;
			if(dep[v]) continue;
			qu.push(v);
			dep[v] = dep[u] + 1;
			fa[v][0] = u;
			ma[v][0].fi = len,ma[v][0].se = -1;
			for(int i = 1;i <= 20;i++){
				int faa = fa[v][i - 1];
				fa[v][i] = fa[faa][i - 1];
				ma[v][i].fi = max(ma[v][i-1].fi,ma[faa][i-1].fi);
				if(ma[v][i-1].fi == ma[faa][i-1].fi) ma[v][i].se = max(ma[v][i-1].se,ma[faa][i-1].se);
				else ma[v][i].se = min(ma[v][i-1].fi,ma[faa][i-1].fi);
			}
		}
	}
}

int d[N];
int lca(int x,int y,int w){
	int idx = 0;
	if(dep[x] < dep[y]) swap(x,y);//让x深度更深
	for(int i = 20;i >= 0;i--){//到同一深度
		if(dep[fa[x][i]] >= dep[y]){
			d[++idx] = ma[x][i].fi;
			d[++idx] = ma[x][i].se;
			x = fa[x][i];
		}
	}
	if(x != y){
		for(int i = 20;i >= 0;i--){
			if(fa[x][i] != fa[y][i] || i == 0){
				d[++idx] = ma[x][i].fi;
				d[++idx] = ma[x][i].se;
				d[++idx] = ma[y][i].fi;
				d[++idx] = ma[y][i].se;
				x = fa[x][i];
				y = fa[y][i];
				if(i == 0 && x != y)
				    i++;
			}
		}
	}
	int ma = -1;
	for(int i = 1;i <= idx;i++)
		if(d[i] != w && d[i] > ma) ma = d[i];
	if(ma == -1)
		return 1e18;
	return - ma + w;
}

signed main(){
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int x,y,z;cin >> x >> y >> z;
		_ed[i] = {x,y,z};
	}
	kruskal();
	bfs();
	int ans = 1e18;
	for(int i = 1;i <= m;i++){
		if(use[i]) continue;
		ans = min(ans,sum + lca(_ed[i].u,_ed[i].v,_ed[i].len));
	}
	cout << ans << endl;
}