次小生成树

没有什么说的，代码就是长

题目

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么需要满足：(value(e) 表示边 e的权值)

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

输入

第一行包含两个整数N 和M，表示无向图的点数与边数。接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

输出

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

样例

输入

输出

/*************************************************************************
  > Author: Henry Chen
  > Mail: 390989083@qq.com 
 ************************************************************************/
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e16;
const int maxn = 200009;
const int maxm = 700009;
int head[maxm],nxt[maxm];
int tot;
int fa[maxm];
int n,m;
int f[maxn][32],dep[maxn];
long long dp[2][maxn][32];
long long val1,val2,ans;
struct Edge
{
    int u,v,w,vis;
} eg[maxm];
struct edge
{
    int v,w;
}e[maxm];
int cmd(Edge a,Edge b)
{
    return a.w < b.w;
}
void add_edge(int u,int v,int w)
{
    e[++tot] = (edge){v,w};
    nxt[tot] = head[u];
    head[u] = tot;
}
int find(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void Kruskal()
{
    sort(eg+1,eg+1+m,cmd);
    for(int i = 1;i <= m;i++)
    {
        int fu = find(eg[i].u);
        int fv = find(eg[i].v); 
        if (fu == fv)
        {
            continue;
        }
        eg[i].vis = 1;
        fa[fu] = fv;
        ans += eg[i].w;
        add_edge(eg[i].u,eg[i].v,eg[i].w);
        add_edge(eg[i].v,eg[i].u,eg[i].w);
    }
}
void dfs(int u,int father,int deep)
{
    dep[u] = deep;
    for(int i = head[u];i != -1;i = nxt[i])
    {
        int v = e[i].v;
        if(v == father) continue;
        dp[0][v][0] = e[i].w;
        dp[1][v][0] = -inf;
        f[v][0] = u;
        for(int t = 1;t <= (int)log2(dep[u]+1);t++)
        {
            f[v][t] = f[f[v][t-1]][t-1];
            if(dp[0][v][t-1]!=dp[0][f[v][t-1]][t-1])
            {
                dp[0][v][t] = max(dp[0][v][t-1],dp[0][f[v][t-1]][t-1]);
                dp[1][v][t] = min(dp[0][v][t-1],dp[0][f[v][t-1]][t-1]);
            }
            else
            {
                dp[0][v][t] = dp[0][v][t-1];
                dp[1][v][t] = max(dp[1][v][t-1],dp[1][f[v][t-1]][t-1]);
            }
        }
    }
    for(int i = head[u];i != -1;i = nxt[i])
    {
        int v = e[i].v;
        if(v == father)
            continue;
        dfs(v,u,deep+1);
    }
}
void update2(int x)
{
    if(x > val1)
    {
        val2 = val1;
        val1 = x;
    }
    else if(x > val2 && x != val1)
    {
        val2 = x;
    }
}
void update(int u, int t)
{
    //printf("!%d %d
",u,t);
    update2(dp[0][u][t]);
    update2(dp[1][u][t]);
}
void lca(int u, int v)
{
    val1 = val2 = -inf;
    if(dep[u] < dep[v])
    {
        swap(u,v);
    }
    while(dep[u] > dep[v])
    {
        int t = (int)log2(dep[u]-dep[v]);
        update(u,t);
        u = f[u][t];
    }
    if(u == v)
        return;
    for(int t = (int)log2(dep[u]);t >= 0;t--)
    {
        if(f[u][t] != f[v][t])
        {
            update(u,t);
            update(v,t);
            u = f[u][t];
            v = f[v][t];
        }
    }
    update(u,0),update(v,0);
}
int main()
{
    memset(head,-1,sizeof(head));
    tot = 0;
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        fa[i] = i;
    }
    for(int i = 1;i <= m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        eg[i] = (Edge){u,v,w};
    }
    Kruskal();
    dfs(1,1,0);
    long long mn = inf;
    for(int i = 1;i <= m;i++)
    {
        //printf("%d %d %d %d
",eg[i].u,eg[i].v,eg[i].w,eg[i].vis);
        if(!eg[i].vis)
        {
            lca(eg[i].u,eg[i].v);
            //printf("%d %d
",val1,val2);
            if(val1 != eg[i].w)
            {
                mn = min(mn,ans-val1+eg[i].w);
            }
            else
            {
                mn = min(mn,ans-val2+eg[i].w);
            }
        }
    }
    printf("%lld
",mn);
    return 0;
}

提示

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。