严格次小生成树（LCA+Kruskal）

一、次小生成树

次小生成树是指在给定的无向图中，如果存在最小生成树和次小生成树，那么对于任何一颗最小生成树来看，都存在一颗次小生成树，使得这两棵树只有一条边不同。次小生成树的边权和大于等于最小生成树的另一颗树，也就是边权之和第二小的生成树。如果有严格次小生成树和非严格次小生成树之分，边权之和严格大于最小生成树的且权值最小的树，就是严格次小生成树。若求得的另一颗树与最小生成树权值相等，则为非严格的次小生成树。

非树边w的值域是一定$\ge$dist1 否则在当w$<$dist1,则之前kruskal求最小生成树的时候把w替换dist1连接a和b，就得到一个更小的生成树（看下图所示）。

---

二、如何求次小生成树？

从非树边中找到一条严格大于树边的边取而代之,至于去掉树中哪条边.因为要求数的权值次小,所以我们发现只要去掉树中最大边就可以让树的权值尽可能的小,然后从所有非树边中找一条边取代树中最大的边,每次取一次Min就可以找到次小生成树。

---

三、LCA+Kruskal

题目：次小生成树

给定一张 $N$个点 $M$条边的无向图，求无向图的严格次小生成树。
设最小生成树的边权之和为 $sum$，严格次小生成树就是指边权之和大于 $sum$的生成树中最小的一个。

输入格式
第一行包含两个整数 $N$ 和 $M$。

接下来 $M$行，每行包含三个整数 $x$，$y$，$z$，表示点 $x$和点 $y$之前存在一条边，边的权值为 $z$。

输出格式
包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

数据范围
$N\le 10^5,M\le 3\times 10^5$
$1\le x,y\le N$
$0\le z\le 10^6$
输入样例：
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
输出样例：
11

AC代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;

const int N=1e5+10,M=6*N,INF=0x3f3f3f3f;
typedef long long ll;

int h[N],e[M],ne[M],w[M],idx;
int n,m;
int p[N];
int f[N][20];  //f[i][j]:i点跳2^j次能跳到的点.
int d1[N][20],d2[N][20];  //d1[i][j]:i点到2^j路径中跳的最大边,d2[i][j]:i点到2^j路径中跳的次大边
int depth[N];
bool st[N];

struct Edge{
    int a,b,c;
    bool used=false;   //该边是否被在树中

    bool operator<(const Edge &t)const{
        return c<t.c;
    }
}edge[M];

//并查集
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

//求最小生成树
ll kruskal(){
    ll res=0;
    for(int i=1;i<=n;i++) p[i]=i;
    sort(edge,edge+m);

    for(int i=0;i<m;i++){
        int pa=find(edge[i].a),pb=find(edge[i].b),c=edge[i].c;
        if(pa!=pb){
            edge[i].used=true;
            p[pa]=pb;
            res+=c;
        }
    }
    return res;
}

//建立最小生成树图
void build(){
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        if(edge[i].used){
            int a=edge[i].a,b=edge[i].b,c=edge[i].c;
            add(a,b,c);
            add(b,a,c);
        }
    }
}

//预处理
void bfs(){
    memset(depth,0x3f,sizeof depth);
    queue<int> q;
    depth[0]=0;
    depth[1]=1;
    q.push(1);
    st[1]=true;

    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(depth[j]>depth[t]+1){
                depth[j]=depth[t]+1;
                f[j][0]=t;
                d1[j][0]=w[i],d2[j][0]=-INF;

                for(int k=1;k<=16;k++){
                    int one_step=f[j][k-1];
                    f[j][k]=f[one_step][k-1];

                    int dist[]={d1[j][k-1],d2[j][k-1],d1[one_step][k-1],d2[one_step][k-1]};

                    for(int u=0;u<4;u++){
                        int d=dist[u];
                        if(d>d1[j][k]){
                            d2[j][k]=d1[j][k];
                            d1[j][k]=d;
                        }
                        else if(d!=d1[j][k] && d>d2[j][k]) d2[j][k]=d;
                    }
                }

                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}

//寻找a和b路径中数的最大边
int lca(int a,int b,int c){

    int dist[N*3];
    int cnt=0;

    if(depth[a]<depth[b]) swap(a,b);

    for(int k=16;k>=0;k--){
        if(depth[f[a][k]]>=depth[b]){
            dist[cnt++]=d1[a][k];
            dist[cnt++]=d2[a][k];
            a=f[a][k];
        }
    }

    if(a!=b){
        for(int k=16;k>=0;k--){
            if(f[a][k]!=f[b][k]){
                dist[cnt++]=d1[a][k];
                dist[cnt++]=d2[a][k];
                dist[cnt++]=d1[b][k];
                dist[cnt++]=d2[b][k];
                a=f[a][k];
                b=f[b][k];
            }
        }

        //跳的最后一步
        dist[cnt++]=d1[a][0];
        dist[cnt++]=d1[b][0];
        dist[cnt++]=d2[a][0];
        dist[cnt++]=d2[b][0];
    }

    int dist1=-INF,dist2=-INF;
    for(int i=0;i<cnt;i++){
        int d=dist[i];
        if(d>dist1){
            dist2=dist1;
            dist1=d;
        }
        else if(d!=dist1 && d>dist2){
            dist2=d;
        }
    }

    if(c!=dist1 && c>dist1) return c-dist1;
    if(c!=dist2 && c>dist2) return c-dist2;

    return INF;

}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge[i]={a,b,c};
    }

    ll sum=kruskal();  //最小生成树的权值

    build();   //建立最小生成树

    bfs();   //预处理f,depth,d1,d2

    ll ans=1e18;

    for(int i=0;i<m;i++){
        if(edge[i].used==false){
            int a=edge[i].a,b=edge[i].b,c=edge[i].c;
            ans=min(ans,sum+lca(a,b,c));
        }
    }

    printf("%lld",ans);
    return 0;

}