题解 P4180 【[Beijing2010组队]次小生成树Tree】
题意：求边权第二小的生成树。
首先做一遍最小生成树。
考虑次小生成树对于最小生成树来说只改变一条边.
所以我们可以枚举每一条不在最短路上的边。
用树上倍增查出这条边的两个端点在最小生成树上的路径上的边的最大值和次大值（其相当于把这条边连起来,这时形成了一个环，看把最大边还是次大边删掉，能使其形成次小生成树），
然后和当前边计算一下差值，取其小者加上即可.
（当然树链剖分+ST表也可）
注意开long long和开够空间
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2000005;
ll n,m,cnt,f[N],h[N],vis[N],d[N];
ll ans=1e18,s,ant1[N/10][25],ant2[N/10][25];//ant1存祖先，ant2存最大值
struct xzy
{
int u,v;ll w;
bool operator < (const xzy &p)
{
return w<p.w;
}
}a[N];
struct Edge
{
int to,next;ll w;
}e[N];
il void add(re int u,re int v,re ll w)
{
e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;
e[++cnt]=(Edge){u,h[v],w};h[v]=cnt;
}
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int find(re int x){return f[x]==x?x:f[x]=find(f[x]);}
il void kruskal()
{
ll ans=0;
fp(i,1,n) f[i]=i;
sort(a+1,a+1+m);
fp(i,1,m)
{
re int u=find(a[i].u),v=find(a[i].v);
if(u!=v) f[u]=v,s+=a[i].w,add(a[i].u,a[i].v,a[i].w),vis[i]=1;
}
}
il void dfs(re int u,re int fa,re int deep)//预处理深度
{
ant1[u][0]=fa;d[u]=deep;
for(re int i=h[u];i;i=e[i].next)
{
re int v=e[i].to;
if(v==fa) continue;
ant2[v][0]=e[i].w;
dfs(v,u,deep+1);
}
}
il int getLCA(re int x,re int y)
{
if(d[x]<d[y]) swap(x,y);
while(d[x]^d[y]) x=f[x];
while(x^y) x=f[x],y=f[y];
return x;
}
il void work()//预处理倍增数组
{
fp(j,1,20)
fp(i,1,n)
{
ant1[i][j]=ant1[ant1[i][j-1]][j-1];
ant2[i][j]=max(ant2[ant1[i][j-1]][j-1],ant2[i][j-1]);
}
}
il ll getmax(re int x,re int y,re ll z)
{
if(y==-1) return 0;
if(ant2[x][y]==z) return max(getmax(x,y-1,z),getmax(ant1[x][y-1],y-1,z));
return ant2[x][y];
}
il ll Query(re int x,re int y,re ll z)//树上倍增找出最大次大值
{
ll mx=0;
if(d[x]<d[y]) swap(x,y);
if(d[x]^d[y])
fq(i,20,0)
if(d[ant1[x][i]]>=d[y]) mx=max(mx,getmax(x,i,z)),x=ant1[x][i];
if(x==y) return z-mx;
fq(i,20,0)
if(ant1[x][i]^ant1[y][i])
{
mx=max(mx,max(getmax(x,i,z),getmax(y,i,z)));
x=ant1[x][i],y=ant1[y][i];
}
return z-max(mx,max(getmax(x,0,z),getmax(y,0,z)));
}
int main()
{
n=gi();m=gi();
fp(i,1,m) a[i].u=gi(),a[i].v=gi(),a[i].w=gi();
kruskal();//最小生成树
dfs(1,1,1);
work();
fp(i,1,m)
if(!vis[i])//在最小生成树外的边
{
re ll q=Query(a[i].u,a[i].v,a[i].w);
if(q) ans=min(ans,s+q);
}
printf("%lld\n",ans);
return 0;
}