严格次小生成树

严格次小生成树是在最小生成树的基础上拓展的问题，它是将最小生成树中断掉一根树的，然后接上另一个边比他大的边形成的。

所以在构建严格次小生成树的时候，我们需要先生成一个最小生成树。

严格： 严格的意思是不能取等

最小生成树的建立

首先，我们需要在给定的图中建立最小的生成树，而为了简化后续的操作，我们选择使用Kruscal算法建树。 Kruscal

加边

通过加边的方式，让原本的树中出现环，然后将环上最大的边减去。这样加的边就可以让生成树尽可能的变小，

for( re int i=1;i<=cnt;i++ )
  {
    if( P[edge[i].id] || edge[i].from==edge[i].to  )  continue; //如果这个边之前被用过/是自环，那么我们就跳过
    int p=solve( edge[i].from , edge[i].to , edge[i].w );
   //记录未加边前的u、v节点之间路径的最大边权 
   int temp=sum1+edge[i].w-p;  //让生成树的大小为 最小生成树的大小+目前加的边-环上的最大边
    if( temp<ans && temp>sum1 && temp!=sum1+edge[i].w )    
{  //如果目前我们的生成树的大小是小于答案的，同时是大于最小生成树的，并且保证了大小的。那么答案更新
      ans=temp;
    }
  }

环上最大边权

那么问题就出现了，我们怎么样去找环上的最大边权呢？

问题就变成了树上路径问题，即 u-v 路径的最大路径。

方法：树链剖分

将建立的生成树保存下来，然后对他进行树链剖分，要求 u-v 的路径最大值时，我们只需要跑链和线段树就可以了。

完整Code

#include<bits/stdc++.h>
#define re register
#define N 200012
#define M 600012
#define inf 12345678900000000
#define int long long
using namespace std;
int head[N],dis[N],u,v,w,n,m;
int cnt,tot,f[N],fa[N],id[N];
int siz[N],son[N],top[N],nu;
int W[N],a[N],deep[N];
int P[M];
struct node1{
  int from,to,w;
  int id;
  bool operator < ( const node1 other ) const
  {
    return w<other.w;
  }
}edge[M];

struct {
  int to,nex,w;
}e[M];

struct node{
  int ma,ma2;
}Q[M];

void addedge(int u,int v,int w)
{
  tot++;
  e[tot]={ v,head[u],w };
  head[u]=tot;
}

int read()
{
  re char c = getchar();
  int x=0,f=1;
  while( c<'0' || c>'9' )
  {
    if( c=='-' ) f=-1;
    c=getchar();
  }
  while( c>='0' && c<='9' )
  {
    x=x*10+c-'0';
    c=getchar();
  }
  return x*f;
}

int find(int x)
{
  if( x==f[x] ) return x;
  return f[x]=find(f[x]);
}

void dfs1(int x)
{
  siz[x]=1;
  int maxson=-1;
  for(re int i=head[x];i;i=e[i].nex)
  {
    int y=e[i].to;
    if( y==fa[x] ) continue;
    W[y]=e[i].w;
    fa[y]=x;
    deep[y]=deep[x]+1;
    dfs1(y);
    siz[x]+=siz[y];
    if( siz[y]>maxson )
    {
      son[x]=y;
      maxson=siz[y];
    }
  }
}

void dfs2(int x,int topf)
{
  top[x]=topf;
  nu++;
  id[x]=nu;
  a[nu]=W[x];
  if( !son[x] ) return;
  dfs2(son[x],topf);
  for(int i=head[x];i;i=e[i].nex)
  {
    int y=e[i].to;
    if( y==fa[x] || y==son[x] ) continue;
    dfs2(y,y);
  }
}

#define lc x<<1
#define rc x<<1|1

int getma2(int a,int b,int c,int d)
{
  int h[5]={a,b,c,d};
  sort( h ,h+4 );
  for(re int i=3;i>=0;i--)
  {
    if( h[i]!=h[3] ) return h[i];
  }
}

void build(int x,int l,int r)
{
  if( l==r )
  {
    Q[x]={ a[l],-inf };
    return;
  }
  int mid=l+r>>1;
  build( lc , l , mid );
  build( rc , mid+1 ,r);
  Q[x].ma=max( Q[lc].ma,Q[rc].ma );
  Q[x].ma2=getma2( Q[lc].ma,Q[lc].ma2,Q[rc].ma,Q[rc].ma2 );
}

node query(int x,int l,int r,int L,int R)
{
  if( L<=l and r<=R )
  {
    return Q[x];
  }
  re int mid=l+r>>1;
  re node temp={ -inf , inf };
  if( L<=mid )
  {
    temp=query( lc , l , mid , L , R );
  }
  if( R>mid )
  {
    node temp2=query( rc , mid+1 , r , L , R );
    temp.ma=max( temp.ma , temp2.ma );
    temp.ma2=getma2( temp.ma , temp2.ma , temp.ma2 , temp2.ma2 );
  }
  return temp;
}

int solve(int u,int v,int w)
{
  int k=-inf;
  while( top[u]!=top[v] )
  {
    if( deep[  top[u]  ] < deep[  top[v]  ] )
    {
      swap( u , v );
    }
    node temp=query( 1 , 1 , n , id[ top[u] ] , id[ u ] );
    if( temp.ma==w ) k=max( k , temp.ma2 );
    else k=max( k , temp.ma );
    u=fa[ top[u] ];
  }
  if( deep[ u ] > deep[v] ) swap( u , v );
  node temp=query( 1 , 1 , n , id[ u ] + 1 , id[ v ] );
  if( temp.ma==w ) k=max( k , temp.ma2 );
  else k=max( k , temp.ma );
  return k;
}

main(){
  //freopen( "P4180_7.in" , "r" , stdin );
  n=read();
  m=read();
  for( re int i=1;i<=n;i++ ) f[i]=i;
  for( re int i=1;i<=m;i++)
  {
    u=read(),v=read(),w=read();
    edge[++cnt]={ u,v,w,i };
    edge[++cnt]={ v,u,w,i };
  }
  sort( edge+1,edge+cnt+1 );
  int sum1=0;
  //cout<<endl;
  for(re int i=1;i<=cnt;i++)
  {
    int u=edge[i].from,v=edge[i].to,w=edge[i].w;
    int a=find( u ),b=find( v );
    if( a==b ) continue;
    sum1+=w;
    P[edge[i].id]=1;
    f[a]=b;

    addedge( u , v , w );
    addedge( v , u , w );
    //cout<<edge[i].from<<" "<<edge[i].to<<" "<<edge[i].w<<endl;
  }
  int ans=inf;
  dfs1(1);
  dfs2(1,1);
  build(1,1,n);
  //cout<<"!!!!";
  //cout<<endl;
  //cout<<sum1<<endl;
  // cout<<endl;
  for( re int i=1;i<=cnt;i++ )
  {
    if( P[edge[i].id] || edge[i].from==edge[i].to  ) continue;
    int p=solve( edge[i].from , edge[i].to , edge[i].w );
    int temp=sum1+edge[i].w-p;
    if( temp<ans && temp>sum1 && temp!=sum1+edge[i].w )
    {
      ans=temp;
      //cout<<ans<<endl;
      //cout<<edge[i].from<<" "<<edge[i].to<<" "<<edge[i].w<<endl;
    }
  }
  printf("%lld",ans);
}