[文章目录]
Description
求一个无向图的严格次小生成树。n<=10^5 m<=3*10^5
所有非树边的权值都会大于等于在最小生成树上覆盖的树边中的权值的最大值，次小生成树上的边同理。
假使小于，发现最小生成树可以更优，不成立。
那么假使一条边在生成树上使得生成树为次小生成树，当且仅当可以代替一条最小生成树上的树边使得总权值增大。
求最小生成树，枚举非树边，倍增求覆盖的树边中比其小且最大的权值，维护最大和次大即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 101000
const int inf=0x3f3f3f3f;
typedef long long ll;
ll ans,sum;
int n,m,fa[N];
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
struct node
{
int x,y,z;
}a[N*3];
bool vis[N*3];
bool cmp(node x,node y){return x.z<y.z;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int head[N],to[N<<1],nxt[N<<1],f[N<<1],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
int Fa[N][20],deep[N],Log[N],mx[N][20],mxx[N][20];
inline int Max(int x,int y){return x>y?x:y;}
void dfs(int x,int pre)
{
for(int i=1;i<=Log[deep[x]];++i)
{
Fa[x][i]=Fa[Fa[x][i-1]][i-1];
mx[x][i]=Max(mx[x][i-1],mx[Fa[x][i-1]][i-1]);
if(mx[x][i-1]!=mx[x][i]) mxx[x][i]=Max(mxx[x][i],mx[x][i-1]);
if(mx[Fa[x][i-1]][i-1]!=mx[x][i]) mxx[x][i]=Max(mxx[x][i],mx[Fa[x][i-1]][i-1]);
if(mxx[x][i-1]!=mx[x][i]) mxx[x][i]=Max(mxx[x][i],mxx[x][i-1]);
if(mxx[Fa[x][i-1]][i-1]!=mx[x][i]) mxx[x][i]=Max(mxx[x][i],mxx[Fa[x][i-1]][i-1]);
}
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
mx[to[i]][0]=f[i];
Fa[to[i]][0]=x;
deep[to[i]]=deep[x]+1;
dfs(to[i],x);
}
}
int Mx,Mxx;
inline void doit(const int x)
{
if(x>Mx) Mxx=Mx,Mx=x;
else if(x!=Mx&&x>Mxx) Mxx=x;
}
ll getcut(int x,int y,ll z)
{
if(deep[x]<deep[y]) swap(x,y);
Mx=Mxx=-inf;
int t=deep[x]-deep[y],i;
while(t)
{
i=Log[-t&t];
doit(mx[x][i]);
doit(mxx[x][i]);
x=Fa[x][i];
t-=-t&t;
}
if(x==y) return z==Mx ? z-Mxx : z-Mx;
for(i=Log[deep[x]];i>=0;--i) if(Fa[x][i]!=Fa[y][i])
{
doit(mx[x][i]); doit(mxx[x][i]);
doit(mx[y][i]); doit(mxx[y][i]);
x=Fa[x][i]; y=Fa[y][i];
}
doit(mx[x][0]); doit(mxx[x][0]);
doit(mx[y][0]); doit(mxx[y][0]);
return z==Mx ? z-Mxx : z-Mx;
}
int main()
{
read(n); read(m);
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
for(int i=1;i<=m;++i)
{
read(a[i].x);
read(a[i].y);
read(a[i].z);
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;++i)
if(find(a[i].x)!=find(a[i].y))
{
add(a[i].x,a[i].y,a[i].z);
fa[fa[a[i].x]]=fa[a[i].y];
vis[i]=1; sum+=a[i].z;
}
memset(mx,0xef,sizeof mx); memset(mxx,0xef,sizeof mxx);
dfs(1,0);
ans=sum+0x3f3f3f3f3f3f3f3fll;
for(int i=1;i<=m;++i) if(!vis[i])
ans=min(ans,sum+getcut(a[i].x,a[i].y,a[i].z));
printf("%lld",ans);
return 0;
}