[BJWC2010] 严格次小生成树

我的代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> PII;
struct edge{
	int l,r,use;
	long long w;
}a[300001];
int n,m,fa[100001],f[100001][21],dep[100001];
long long sum,ans=1e16,g[100001][21][2];
vector <PII> G[100001];
int find(int x){
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
bool cmp(edge a,edge b){
	return a.w<b.w;
}
void dfs(int rt,int fa,long long edge){
	dep[rt]=dep[fa]+1;
	f[rt][0]=fa;
	g[rt][0][0]=edge;
	g[rt][0][1]=-1e16;
	for(int i=1;i<=20;i++){
		f[rt][i]=f[f[rt][i-1]][i-1];
		g[rt][i][0]=max(g[rt][i-1][0],g[f[rt][i-1]][i-1][0]);
		if(g[rt][i-1][0]==g[f[rt][i-1]][i-1][0]) g[rt][i][1]=max(g[rt][i-1][1],g[f[rt][i-1]][i-1][1]);
		if(g[rt][i-1][0]<g[f[rt][i-1]][i-1][0]) g[rt][i][1]=max(g[rt][i-1][0],g[f[rt][i-1]][i-1][1]);
		if(g[rt][i-1][0]>g[f[rt][i-1]][i-1][0]) g[rt][i][1]=max(g[rt][i-1][1],g[f[rt][i-1]][i-1][0]);
	}
	for(int i=0;i<G[rt].size();i++){
		int to=G[rt][i].first;
		long long w=G[rt][i].second;
		if(to!=fa) dfs(to,rt,w);
	}
}
PII find(int u,int v){
	long long r1=-1e16,r2=-1e16;
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=20;i>=0;i--){
		if(dep[f[u][i]]>=dep[v]){
			r1=max(r1,g[u][i][0]);
			r2=max(r2,g[u][i][1]);
			u=f[u][i];
		}
	}
	if(u==v) return make_pair(r1,r2);
	for(int i=20;i>=0;i--){
		if(f[u][i]!=f[v][i]){
			r1=max(r1,max(g[u][i][0],g[v][i][0]));
			r2=max(r2,max(g[u][i][1],g[v][i][1]));
			u=f[u][i];
			v=f[v][i];
		}
	}
	return make_pair(max(r1,max(g[u][0][0],g[v][0][0])),max(r2,max(g[u][0][1],g[v][0][1])));
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld",&a[i].l,&a[i].r,&a[i].w);
		a[i].use=0;
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++){
		int x=find(a[i].l),y=find(a[i].r);
		if(x==y) continue;
		fa[x]=y;
		sum+=a[i].w;
		a[i].use=1;
		G[a[i].l].push_back(make_pair(a[i].r,a[i].w));
		G[a[i].r].push_back(make_pair(a[i].l,a[i].w));
	}
	dfs(1,0,0);
	for(int i=1;i<=m;i++){
		if(a[i].use) continue;
		PII aus=find(a[i].l,a[i].r);
		if(a[i].w>aus.first) ans=min(ans,sum-aus.first+a[i].w);
		if(a[i].w==aus.first) ans=min(ans,sum-aus.second+a[i].w);
	}
	printf("%lld",ans);
	return 0;
}