模拟赛 7 道题，这是最后一道，我一共做了 3.2 道，这是我做的第二道

题目传送门： 严格次小生成树

感觉我对紫题有点脱敏了

题目思路

考虑到我暑假做过货车运输（暑假写的做题笔记）以及一些最小生成树有关的性质题，所以挺快就胡出思路了

最小生成树性质（复制于我暑假写的笔记）：

我推出了一个性质，对于非树边 ($u,v$)，若将它的权值降低至 小于等于 原最小生成树上 $u,v$ 之间唯一链上边权最大的边，则边 ($u,v$) 是新的最小生成树上的边。

感觉写的挺抽象的，但！我！不！会！画！图！的！

这个性质其实是这样的：若边 ($u,v$) 是非树边，则该边权值大于原最小生成树上 $u,v$ 之间唯一链上任意一边的边权。

这个其实画个图推推就能推出来了，所以就不证明了。其实是我不会。

那么我们感性理解一下：

既然一条非树边距离最小生成树只差临门一脚，所以次小生成树一定是替换了某一条非树边的结果。

所以对于每一条非树边我们这么考虑：

• 把这条边加入最小生成树，就会形成一个环，再把环中任意一条树边断掉，就会形成一个新的生成树，我们显然希望这个生成树尽可能小，所以一定会断掉最大的树边
• 计算出新生成树的大小，由于对每一个新生成树取最小就是次小生成树

实现

也就是说问题转换成了快速维护树上链的最大值

~显然可以树剖~由于不涉及修改倍增维护即可~其实就是我树剖写挂了~

但是没完

容易发现当最小生成树不唯一时得出的答案不严格，错误的处理方法是忽略和最小生成树等权的情况，小样例就可以卡掉

正解：倍增同时维护一个严格次大值，如果出现等权情况就替换掉严格次大值而不是最大值，具体细节看代码吧

代码贴上

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=3e5+5;
const int L=20,INF=1e18;
int fa[N];
int up[L][N],maxn[L][N],minn[L][N];//maxn最大minn次大 
int dep[N];
struct node{
	int x,y,w;
	bool tr;//是否为树边 
}e[N]; 
struct edge{
	int to,nxt,v;
}chk[N];//链式前向星存最小生成树 
bool cmp(node a,node b){return a.w<b.w;}
int findF(int x){
	if(x==fa[x]) return x;
	fa[x]=findF(fa[x]);
	return fa[x];
}
int head[N];
int n,m,u,v,w,cnt,sum,ant;
void add(int x,int y,int w){
	chk[++ant].to=y;
	chk[ant].nxt=head[x];
	chk[ant].v=w;
	head[x]=ant;
}
void dfs(int u,int ff,int elen){//倍增预处理 
	up[0][u]=ff;
	maxn[0][u]=elen;
	minn[0][u]=-INF;
	dep[u]=dep[ff]+1;
	for(int i=head[u];i;i=chk[i].nxt){
		int dd=chk[i].to;
		if(dd==ff) continue;
		dfs(dd,u,chk[i].v);
	}

}
void pp(int n,int root){
	dep[root]=-1;
	dfs(root,root,0);
	for(int k=1;k<L;k++){
		for(int x=1;x<=n;x++){
			up[k][x]=up[k-1][up[k-1][x]];
			//在4中可能的更新中找到最大和严格次大 
			int val1=maxn[k-1][x];
            int val2=maxn[k-1][up[k-1][x]];
            int val3=minn[k-1][x];
            int val4=minn[k-1][up[k-1][x]];
            int first=-INF,second=-INF;
            for(int v:{val1,val2,val3,val4}) {
                if(v>first){
                    second=first;
                    first=v;
                }else if(v!=first&&v>second) {
                    second=v;
                }
            }     
            maxn[k][x] = first;
            minn[k][x] = second;
		} 
	}
}
int getedge(int u,int v){//查询最大值 
	int res=-INF;
	if(dep[u]<dep[v])swap(u,v);
	for(int k=L-1;k>=0;k--){
		if(dep[up[k][u]]>=dep[v]){
			res=max(res,maxn[k][u]);
			u=up[k][u];
		}
	}
	if(u==v) return res;
	for(int k=L-1;k>=0;k--){
		if(up[k][u]!=up[k][v]){
			res=max(res,maxn[k][u]);
			res=max(res,maxn[k][v]);
			u=up[k][u];
			v=up[k][v];
		}
	}
	res=max(res,maxn[0][u]);
	res=max(res,maxn[0][v]);
	return res;
}
int getminer(int u,int v,int mx){//查询严格次大值 
	int res=-INF;
	if(dep[u]<dep[v])swap(u,v);
	for(int k=L-1;k>=0;k--){
		if(dep[up[k][u]]>=dep[v]){
			if(maxn[k][u]!=mx){
				res=max(res,maxn[k][u]);
			}else{
				res=max(res,minn[k][u]);
			}
			u=up[k][u];
		}
	}
	if(u==v) return res;
	for(int k=L-1;k>=0;k--){
		if(up[k][u]!=up[k][v]){
			if(maxn[k][u]!=mx){
				res=max(res,maxn[k][u]);
			}else{
				res=max(res,minn[k][u]);
			}
			if(maxn[k][v]!=mx){
				res=max(res,maxn[k][v]);
			}else{
				res=max(res,minn[k][v]);
			}
			u=up[k][u];
			v=up[k][v];
		}
	}
	if(maxn[0][u]!=mx){
		res=max(res,maxn[0][u]);
	}else{
		res=max(res,minn[0][u]);
	}
	if(maxn[0][v]!=mx){
		res=max(res,maxn[0][v]);
	}else{
		res=max(res,minn[0][v]);
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		cin >> u >> v >>w;
		e[++cnt].x=u;e[cnt].y=v;e[cnt].w=w;
		e[cnt].tr=0;
	}
	//克鲁斯卡尔 
	sort(e+1,e+cnt+1,cmp);
	int k=0,tot=0;
	for(int i=1;i<=cnt;i++){
		if(findF(e[i].x)!=findF(e[i].y)){
			tot+=e[i].w;
			fa[findF(e[i].x)] = findF(e[i].y);
			add(e[i].x,e[i].y,e[i].w);
			add(e[i].y,e[i].x,e[i].w);
			k++;e[i].tr=1;
			if(k==n-1) break;
		}
	}
	pp(n,1);
	int res=INF;
	for(int i=1;i<=m;i++){
		if(e[i].x==e[i].y) continue;
		if(e[i].tr==0){
			int tmp=getedge(e[i].x,e[i].y);
			if(tmp==e[i].w) {//发现等效替代就改为用次大值 
				tmp=getminer(e[i].x,e[i].y,tmp);
			}
			res=min(res,tot+e[i].w-tmp);
		}
	}
	cout << res;
	return 0;
}