洛谷P4180 [BJWC2010] 严格次小生成树题解

题目链接：P4180 [BJWC2010] 严格次小生成树

题意：

给定一张无向连通图，求出它的严格次小生成树。

如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是 $E_S$，那么需要满足：
$\sum_{(u,v) \in E_M}w(u,v)<\sum_{(u,v) \in E_S}w(u,v)$
输入格式：

第一行包含两个整数 $N$ 和 $M$，表示无向图的点数与边数。

接下来 $M$ 行，每行 $3$ 个数 $x,y,z$ 表示，点 $x$ 和点 $y$ 之间有一条边，边的权值为 $z$。

输出格式：

包含一行，仅一个数，表示严格次小生成树的边权和。

数据中无向图不保证无自环

对于 $100\%$ 的数据， $N\le 10^5$，$M\le 3\times10^5$，边权 $\in [0,10^9]$，数据保证必定存在严格次小生成树。

欠了快一年的题，现在来写好像挺适合的。

注意，「$\Sigma$ 次小 ≤ $\Sigma$ 最小」是 非严格次小，而「$\Sigma$ 次小 < $\Sigma$ 最小」是 严格次小。

一个经典的错误是在 $\mathtt{Kruskal}$ 的过程中，不加入第一条能加入的边。

为什么会错呢，因为你不能保证接下来的一定是次小生成树（甚至不能保证非严格次小）

那么怎么做呢？

考虑枚举每一条不在最小生成树上的边 $(u,v)$ ，然后把它加入最小生成树里

显然此时最小生成树变成了一个基环树，因此我们要断掉环上边权小于 $w(u,v)$ 的最大的边。

不难发现这条边的边权只可能有两种情况（下文用 $u \leadsto v$ 表示在最小生成树 $u$ 到 $v$ 的简单路径）

$u \leadsto v$ 最大的边权 $\mathtt{mx}$，此时一定有 $\mathtt{mx} < w(u,v)$ 。
$u \leadsto v$ 次大的边权 $\mathtt{smx}$ ，此时一定有 $\mathtt{mx} = w(u,v) \land \mathtt{smx} < w(u,v)$

考虑如何维护这个东西。我们可以先跑一遍 $\mathtt{Kruskal}$ 求出一棵最小生成树

然后用树链剖分维护区间最大值&区间次大值。如果没有次大值，那就设为 $-\infty$ 。

这样我们枚举每条边就可以 $\mathcal{O}(\log n)$ 得到一个相对于最小生成树的增量。最小化它的正值即可。

时间复杂度 $\mathcal{O}(n\log n+m\log m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define Fi first
#define Se second
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
    template<typename T> void print(T x) { write(x); pc('\n'); }
}using namespace FastIO;
#define N ((int)(1e5+15))
#define M ((int)(3e5+15))

bitset<M> vis;
int n,m,pos=1,sum,head[N];
struct Edge{ int u,v,w,next; } e[M * 2],e0[M];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
namespace Union
{
    int f[N],sz[N];
    void init(int n) { for(int i=1; i<=n; i++) f[i] = i, sz[i] = 1; }
    int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    bool merge(int u,int v) 
    {
        int x = find(u), y = find(v);
        if(x == y) return 0;
        if(sz[x] < sz[y]) swap(x,y);
        f[x] = y; sz[y] += sz[x];
        return 1;
    }
}
void kruskal()
{
    using namespace Union;
    for(int i=1; i<=m; i++){ read(e0[i].u); read(e0[i].v); read(e0[i].w); }
    init(n); sort(e0+1, e0+1+m, [](Edge a,Edge b){ return a.w < b.w; });
    for(int i=1, cnt=0; i<=m && cnt < n-1; i++)
    {
        int u = e0[i].u, v = e0[i].v, w = e0[i].w;
        if(!merge(u,v)) continue;
        addEdge(u,v,w); addEdge(v,u,w);
        sum += w; vis[i] = 1; ++cnt;
    }
}
namespace SEG
{
    int idx,id[N],dep[N],S[N],fa[N],top[N],sz[N],son[N],val[N];
    void dfs1(int u,int f)
    {
        fa[u] = f; dep[u] = dep[f] + 1; sz[u] = 1; int mx = -1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v; if(v == f) continue;
            // 这里的 S 数组是为了便于边权化点权
            S[v] = S[u] + e[i].w; dfs1(v,u); sz[u] += sz[v];
            if(sz[v] > mx) { mx = sz[v], son[u] = v; }
        }
    }
    void dfs2(int u,int ftop)
    {
        top[u] = ftop; id[u] = ++idx; val[idx] = S[u] - S[fa[u]];
        if(!son[u]) return; dfs2(son[u], ftop);
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            if(v != fa[u] && v != son[u]) dfs2(v,v);
        }
    }
    #define ls(at) (at << 1)
    #define rs(at) (at << 1 | 1)
    struct node { int mx, smx; } tr[N * 4];
    int getsmx(int a,int b,int c,int d)
    {
        int tmp[10] = {-1,a,b,c,d};
        sort(tmp+1, tmp+1+4, greater<int>());
        for(int i=2; i<=4; i++) if(tmp[i] != tmp[1]) return tmp[i];
        return -INF;
    }
    void push_up(int at)
    {
        node &l=tr[ls(at)], &r=tr[rs(at)];
        tr[at].mx = max(l.mx, r.mx);
        tr[at].smx = getsmx(l.mx, l.smx, r.mx, r.smx);
    }
    void build(int l,int r,int at)
    {
        if(l == r) { return tr[at] = {val[l], -INF}, void(0); }
        int mid = (l + r) >> 1;
        build(l,mid,ls(at)); build(mid+1,r,rs(at));
        push_up(at);
    }
    pii query(int nl,int nr,int l,int r,int at)
    {
        if(nr < l || r < nl) return {-INF,-INF};
        if(nl <= l && r <= nr) return {tr[at].mx, tr[at].smx};
        int mid = (l + r) >> 1;
        if(nl > mid) return query(nl,nr,mid+1,r,rs(at));
        if(nr <= mid) return query(nl,nr,l,mid,ls(at));
        pii r1=query(nl,nr,l,mid,ls(at)), r2=query(nl,nr,mid+1,r,rs(at));
        return {max(r1.Fi, r2.Fi), getsmx(r1.Fi, r1.Se, r2.Fi, r2.Se)};
    }
    int qRange(int x,int y,int z)
    {
        int res = -INF; pii r;
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x,y);
            r = query(id[top[x]], id[x], 1,n,1);
            up(res, (r.Fi == z) ? r.Se : r.Fi);
            x = fa[top[x]];
        }
        dep[x] > dep[y] ? swap(x,y) : void(0);
        // 注意边权化点权不要把 id[x] 给算进去
        r = query(id[x]+1, id[y], 1,n,1);
        return max(res, (r.Fi == z) ? r.Se : r.Fi);

    }
    void init() { dfs1(1,0); dfs2(1,1); build(1,n,1); }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m);
    kruskal(); SEG::init(); int ans = INF;
    for(int i=1,cur; i<=m; i++)
    {
        if(vis[i]) continue;
        cur = sum + e0[i].w - SEG::qRange(e0[i].u, e0[i].v, e0[i].w);
        if(ans > cur && cur > sum) ans = cur;
    }
    print(ans);
    return 0;
}