次小生成树

\(\rm 次小生成树\)

一开始只是兴起学一学，思路挺好理解的但是打代码不知道是想复杂了还是怎么的，反正很繁琐，调了一整天

一、定义
非严格次小生成树，即边权和小于等于最小生成树边权和的生成树；严格次小生成树，即边权和大于最小生成树边权和的生成树

二、解法

首先，我们可以证明，次小生成树与最小生成树一定只有一条不同的边。
这是很显然的，因为我们如果选出两条边来替换最小生成树的边，一定是没有只替换一条边优。

那么，对于每一条非树边~(u,v)~，如果我们把它加入生成树，就会形成一个环，我们要从环里删除一条边使仍然构成一棵树，那么要使生成的树边权和尽量小，我们就需要找到这个环里除了边~(u,v)~外最大的一条边（Q:为什么除了边~(u,v)~？A:因为这是我们要加进去的边），即原生成树上u到v的路径上边权最大的一条边。这我们可以通过倍增或者树剖实现。
具体而言，用每个点的点权存储其到其父亲的边的边权。但是这样有一个问题，就是说如果~u,v~不在同一条链上，那么我们要求的其路径上的最大值就是路径~(u,v)~上不包括~lca(u,v)~的所有点的点权最大值。那么怎样实现不包括~lca~呢？
对于倍增，我们只需要使最终求的比~lca~深度大~1~即可。代码如下：

int ans=-inf;
for(int i=20;i>=0;i--){
    if((dep[x]-(1<<i))>dep[y]){
        ans=max(ans,Max[x][i]);
        x=f[x][i];
    }
}
if(f[x][0]==y)return ans;
for(int i=20;i>=0;i--){
    if(f[f[x][i]][0]!=f[f[y][0]]){
        ans=max(ans,max(Max[x][i],Max[y][i]));
        x=f[x][i],y=f[y][i];
    }
}
return ans;
//应该是这样的，反正也没写过，我写的时树剖版本的。

对于树剖，先求出~lca~，在~x~不断向~lca~所在重链链上跳时，如果最终与~lca~重合，那么所求即为前一步的重链的顶，否则是~lca~所在重链的下一个点即在线段树上标号+1的数。代码如下：

il int find(int x,int fu){
    int now=0;
    while(top[x]!=top[fu])now=top[x],x=fa[top[x]];
    if(x==fu)return now;return reflect[id[fu]+1];
}
node now=pushup(query_way(x,find(x,fu)),query_way(y,find(y,fu)));

在求严格次小生成树时，我们需要考虑，如果所考虑的非树边边权和环内最大边边权一样，那么我们还要去找环内的次大边，所以在树剖的线段树上还要维护次大值。

树剖版代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Mid (l+r)/2
#define lson tree[rt].ls,l,Mid
#define rson tree[rt].rs,Mid+1,r
#define int ll
#define il inline
#define rint register int
const int mod=1e9+7,inf=21474836470000000,maxn=300000+5;
int n,m,Q,K;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
int e=1,to[maxn<<1],hed[maxn],nxt[maxn<<1],fr[maxn<<1],w[maxn<<1],vis[maxn<<1];
il void add(int x,int y,int z){
    to[++e]=y;nxt[e]=hed[x];hed[x]=e;w[e]=z;fr[e]=x;
}
int S,ANS=inf+inf+inf;
namespace prim{
    int p[maxn];
    struct node1{
        int x,dis,id;
        bool operator <(const node1 &a)const{return dis>a.dis;}
    };
    priority_queue<node1>q;
    il void work(){
        p[1]=1;
        for(rint i=hed[1];i;i=nxt[i])q.push((node1){to[i],w[i],i});
        int tot=n-1;
        while(tot--){
            while(!q.empty()&&p[q.top().x])q.pop();
            node1 u=q.top();q.pop();
            p[u.x]=1;S+=u.dis;vis[u.id]=vis[(u.id)^1]=1;
            for(rint i=hed[u.x];i;i=nxt[i])if(!p[to[i]])q.push((node1){to[i],w[i],i});
        }
        return;
    }
}
namespace tre_cut{
    int dep[maxn],siz[maxn],son[maxn],fa[maxn],w_data[maxn];
    int top[maxn],cnt,id[maxn],a[maxn],reflect[maxn];
    struct node{int Max,MMax;}tre[maxn<<1];
    struct NODE{int ls,rs;}tree[maxn<<1];
    il void dfs1(int x,int fu,int deep){
        dep[x]=deep;fa[x]=fu;siz[x]=1;
        for(rint i=hed[x];i;i=nxt[i]){
            if(!vis[i]||to[i]==fu)continue;
            dfs1(to[i],x,deep+1);w_data[to[i]]=w[i];
            siz[x]+=siz[to[i]];
            if(siz[to[i]]>siz[son[x]])son[x]=to[i];
        }return;
    }
    il void dfs2(int x,int topx){
        top[x]=topx;id[x]=++cnt;a[cnt]=w_data[x];reflect[cnt]=x;
        if(!son[x])return;dfs2(son[x],topx);
        for(rint i=hed[x];i;i=nxt[i]){
            if(to[i]==fa[x]||to[i]==son[x]||!vis[i])continue;
            dfs2(to[i],to[i]);
        }return;
    }
    int comp[5];
    il node pushup(node ls,node rs){
        comp[1]=ls.Max,comp[2]=ls.MMax,comp[3]=rs.Max,comp[4]=rs.MMax;
        int Max=-inf,MMax=-inf-inf;
        for(rint i=1;i<=4;++i){
            if(comp[i]>Max)MMax=Max,Max=comp[i];
            else if(comp[i]<Max&&comp[i]>MMax)MMax=comp[i];
        }
        return (node){Max,MMax};
    }
    int CNT;
    il void build(int &rt,int l,int r){
        if(!rt)rt=++CNT;
        if(l==r)return (void)(tre[rt]=(node){a[l],-inf});
        build(lson),build(rson);
        tre[rt]=pushup(tre[tree[rt].ls],tre[tree[rt].rs]);
    }
    il node query(int rt,int l,int r,int L,int R){
        if(!rt)return (node){-inf,-inf-inf};
        if(L<=l&&r<=R)return tre[rt];
        node end=(node){-inf,-inf-inf};
        if(L<=Mid)end=pushup(end,query(lson,L,R));
        if(R>Mid)end=pushup(end,query(rson,L,R));
        return end;
    }
    il int lca(int x,int y){
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        return x;
    }
    il void process(){
        dfs1(1,0,1);dfs2(1,1);
        int rt=0;build(rt,1,n);
        return;
    }
    il int find(int x,int fu){
        int now=0;
        while(top[x]!=top[fu])now=top[x],x=fa[top[x]];
        if(x==fu)return now;return reflect[id[fu]+1];
    }
    il node query_way(int x,int y){
        node end=(node){-inf,-inf-inf};
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            end=pushup(end,query(1,1,n,id[top[x]],id[x]));
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        end=pushup(end,query(1,1,n,id[x],id[y]));
        return end;
    }
    il void doit(int x,int y,int z){
        int fu=lca(x,y);
        node now=pushup(query_way(x,find(x,fu)),query_way(y,find(y,fu)));
        int S1=S+z-now.Max,S2=S+z-now.MMax;
        if(S1>S)ANS=min(ANS,S1);
        else if(S2>S) ANS=min(ANS,S2);
        return;
    }
}
signed main(){
    n=read();m=read();
    for(rint i=1;i<=m;++i){
        int x=read(),y=read(),z=read();
        add(x,y,z);add(y,x,z);
    }
    prim::work();tre_cut::process();
    for(int i=2;i<=e;i+=2){
        if(vis[i])continue;
        tre_cut::doit(fr[i],to[i],w[i]);
    }
    printf("%lld\n",ANS);
    return 0;
}

\(\rm 思路极其清晰\)

次小生成树

原文：https://www.cnblogs.com/Zikual/p/12080344.html