次小生成树

Masky · 2019-12-22 17:20:48 · 题解

次小生成树

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

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

\ 二、解法

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

那么，对于每一条非树边(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)));

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

树剖版核心代码如下：

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(){
    for(int i=2;i<=e;i+=2){
        if(vis[i])continue;//vis表示该边是否在最小生成树上
        tre_cut::doit(fr[i],to[i],w[i]);//查询每条非树边的端点u,v在树上的路径中最大的边权
    }
    printf("%lld\n",ANS);
    return 0;
}

思路极其清晰