题解：P14545 [IO 2024 #3] 安全航行

Lonely_Sun · 2026-11-05 17:48:46 · 题解

根据题意，先跑一遍最小生成树。

此时 m 条边被分为两种：

最小生成树上的树边
非最小生成树上的非树边

对于树边，我们考虑这条边什么时候会被替换。

当有 k 条非树边能够重新连接删除这条树边后形成的两个连通块时，这些非树边都可以替换这条树边。

因此，这条树边的答案就是这 k 条非树边边权的最小值。也就是说，为了防止被替换，它的边权必须小于等于所有可以替换它的边。

对于非树边，它在最小生成树上对应一条路径。路径上的每条树边都可以被它替换。

为了让这条非树边能够进入最小生成树，它的边权只需要降到路径上树边边权的最大值即可，因为这样就可以替换路径上的某一条树边。

正确性证明

对于树边 e，删除它后最小生成树分成两个连通块。若存在非树边能够连接这两个连通块，则这些非树边都可以替换 e。为了让 e 仍不被替换，e 的边权不能大于这些非树边的最小值，因此答案取这些非树边边权的最小值。

对于非树边 f，它在最小生成树上对应一条路径。路径上的任意一条树边都可以被 f 替换，因此 f 的边权只需降到这些树边边权的最大值，就能替换其中一条树边进入最小生成树，所以答案取路径上树边边权的最大值。

树链剖分加线段树只是对上述“路径取最大值”和“路径取最小值”操作的维护，不改变答案含义。

朴素暴力

于是我们有了一个朴素的想法：

枚举每一条边，然后把去除第 i 条边后的最小生成树用并查集重新连起来。

接着枚举每一条非树边，利用并查集判断这条边是否可以将破裂的树连起来。如果可以，说明当前这条非树边可以代替枚举出来的树边。

因为这两条边可以互相替代，所以它们都在对方的答案范围内，因此可以同时更新树边与非树边的答案。

:::success[暴力代码]

#include<bits/stdc++.h>
#define ll long long
#define ac read()
using namespace std;
const int N=100005;
const int M=1000006;
inline ll read() {
    ll x=0,f=1;
    int c=getchar();
    while(!isdigit(c)) {
        f=(c=='-')?-1:1;
        c=getchar();
    }
    while(isdigit(c)) {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
int n,m;
struct edge {
    int u,v,val,id;
} e[M];
int fa[N];
bool cmp(edge a,edge b) {
    return a.val<b.val;
}
int Kus[N],cnt;
inline int Find(int x) {
    if(fa[x]==x) return x;
    return fa[x]=Find(fa[x]);
}
int ans[M];
bool vis[M];
int main() {
    n=ac,m=ac;
    for(int i=1; i<=n; ++i) fa[i]=i;
    for(int i=1; i<=m; ++i) {
        int u=ac,v=ac,val=ac;
        e[i]= {u,v,val,i};
        ans[i]=-1e9;
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1; i<=m; ++i) {
        int fu=Find(e[i].u),fv=Find(e[i].v);
        if(fu==fv) continue;
        fa[fu]=fv,Kus[++cnt]=i;
        vis[e[i].id]=1;
    }
    for(int i=1; i<=cnt; ++i) {
        int now=Kus[i];
        int u=e[now].u,v=e[now].v;
        int Min=1e9;
        for(int j=1; j<=n; ++j) fa[j]=j;
        for(int j=1; j<=cnt; ++j) {
            if(i==j) continue;
            int I=Kus[j];
            int fu=Find(e[I].u),fv=Find(e[I].v);
            fa[fu]=fv;
        }
        for(int j=1; j<=m; ++j) {
            if(vis[e[j].id]) continue;
            int fu=Find(e[j].u),fv=Find(e[j].v);
            if(fu!=fv) {

                ans[e[j].id]=max(e[now].val,ans[e[j].id]);
                Min=min(Min,e[j].val);
            }
        }
        ans[e[now].id]=Min;
    }
    for(int i=1; i<=m; ++i) {
        cout<<ans[i]<<"\n";
    }
    return 0;
}

:::

正解

我们可以想象一下一条非树边在树上被连接的样子。

可以看到这条边的两个端点 u、v，两点之间的路径头尾被相连了，成了一个环。

此时树上两点之间的路径上的树边，都可以被这条非树边更新到。

而路径上的树边也可以更新这条非树边的答案。

这个时候看到两点之间的路径，应该想到树上路径操作。

没错，那就是树上轻重链剖分。

我们可以在最小生成树上进行树链剖分。

因为轻重链剖分后的 dfs 序上，不仅子树是连续的区间，重链也是连续的区间。

于是问题转化为树上路径取最大值、路径取最小值，使用树链剖分加线段树维护即可。

直接用线段树维护区间最大值和区间取最小值标记，可以参考 P8024。

然后时间复杂度为 O(m \log m + m \log n \log n)。

来源为最小生成树加上找树上路径同时调用线段树。

两只 log 是可以跑过 m=4 \times 10^5 的。

:::success[AC 代码]

#include<bits/stdc++.h>
#define ll long long
#define ac read()
using namespace std;
const int N=100005;
const int M=1000006;
inline ll read() {
    ll x=0,f=1;
    int c=getchar();
    while(!isdigit(c)) {
        f=(c=='-')?-1:1;
        c=getchar();
    }
    while(isdigit(c)) {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
int n,m;
struct node {
    int nex,to,val,id;
} e[N<<1];
int head[N],tot,a[N];
struct edge {
    int u,v,val,id;
} ed[M<<1];
bool cmp(edge a,edge b) {
    return a.val<b.val;
}
inline void add(int u,int v,int val,int id) {
    e[++tot]= {head[u],v,val,id};
    head[u]=tot;
}
bool vis[M];
int dep[N],son[N],siz[N],Top[N],FA[N];
int b[M],fa[N];
void dfs1(int u,int Fa,int dept) {
    dep[u]=dept;
    FA[u]=Fa;
    siz[u]=1;
    for(int i=head[u]; i!=-1; i=e[i].nex) {
        int to=e[i].to;
        if(to==Fa) continue;
        a[to]=e[i].val;
        b[e[i].id]=to;
        dfs1(to,u,dept+1);
        siz[u]+=siz[to];
        if(siz[son[u]]<siz[to]) son[u]=to;
    }
}
int dfn[N],dfs,DFS[N];
void dfs2(int u,int Tp) {
    dfn[u]=++dfs;
    DFS[dfs]=u;
    Top[u]=Tp;
    if(!son[u]) return ;
    dfs2(son[u],Tp);
    for(int i=head[u]; i!=-1; i=e[i].nex) {
        int to=e[i].to;
        if(to==FA[u]||to==son[u]) continue;
        dfs2(to,to);
    }
}
inline int Find(int x) {
    if(x==fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
struct Tree {
    int l,r;
    int Max,Min;
    int Minn;// 区间取 min 懒标记
} t[N<<2];
inline void upd(int p) {
    t[p].Max=max(t[p<<1].Max,t[p<<1|1].Max);
    t[p].Min=min(t[p<<1|1].Min,t[p<<1].Min);
    return ;
}
inline void build(int p,int l,int r) {
    t[p]= {l,r,(int)-1e9,(int)1e9,(int)1e9};
    if(l==r) {
        t[p].Max=a[DFS[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    upd(p);
}
inline int query_max(int p,int ls,int rs) {
    if(ls<=t[p].l&&t[p].r<=rs) {
        return t[p].Max;
    }
    int mid=(t[p].l+t[p].r)>>1;
    int Max=-1e9;
    if(ls<=mid) Max=max(Max,query_max(p<<1,ls,rs));
    if(mid+1<=rs) Max=max(Max,query_max(p<<1|1,ls,rs));
    return Max;
}
inline void spread(int p) {
    if(t[p].Minn==1e9) return ;
    int l=p<<1,r=p<<1|1;
    t[l].Minn=min(t[p].Minn,t[l].Minn);
    t[r].Minn=min(t[p].Minn,t[r].Minn);
    t[l].Min=min(t[l].Min,t[p].Minn);
    t[r].Min=min(t[r].Min,t[p].Minn);
    t[p].Minn=1e9;
    return ;
}
inline void Caoz_min(int p,int ls,int rs,int num) {
    if(ls<=t[p].l&&t[p].r<=rs) {
        t[p].Minn=min(t[p].Minn,num);
        t[p].Min=min(t[p].Min,num);
        return ;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(ls<=mid) Caoz_min(p<<1,ls,rs,num);
    if(mid+1<=rs) Caoz_min(p<<1|1,ls,rs,num);
    return ;
}
inline int query_min(int p,int x) {
    if(t[p].l==t[p].r) {
        return t[p].Min;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid) return query_min(p<<1,x);
    else return query_min(p<<1|1,x);
}
inline int LCA(int x,int y,int num) {
    int Max=-1e9;
    while(Top[x]!=Top[y]) {
        if(dep[Top[x]]<dep[Top[y]]) {
            Max=max(query_max(1,dfn[Top[y]],dfn[y]),Max);
            Caoz_min(1,dfn[Top[y]],dfn[y],num);
            y=FA[Top[y]];
        } else {
            Max=max(query_max(1,dfn[Top[x]],dfn[x]),Max);
            Caoz_min(1,dfn[Top[x]],dfn[x],num);
            x=FA[Top[x]];
        }
    }
    if(dep[y]<dep[x]) swap(x,y);
    Max=max(Max,query_max(1,dfn[x]+1,dfn[y]));
    Caoz_min(1,dfn[x]+1,dfn[y],num);
    return Max;
}
int Kus[N],cnt;
int ans[M];
int main() {
    memset(head,-1,sizeof head);
    n=ac,m=ac;
    for(int i=1; i<=n; ++i) fa[i]=i;
    for(int i=1; i<=m; ++i) {
        int u=ac,v=ac,val=ac;
        ed[i]= {u,v,val,i};
    }
    sort(ed+1,ed+1+m,cmp);
    for(int i=1; i<=m; ++i) {
        int fu=Find(ed[i].u);
        int fv=Find(ed[i].v);
        if(fu==fv) continue;
        fa[fu]=fv;
        Kus[++cnt]=i;
        vis[i]=true;
        add(ed[i].u,ed[i].v,ed[i].val,ed[i].id);
        add(ed[i].v,ed[i].u,ed[i].val,ed[i].id);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    a[1]=-1e9;
    build(1,1,n);
    for(int i=1; i<=m; ++i) {
        if(vis[i]) continue;
        int u=ed[i].u,v=ed[i].v,val=ed[i].val,id=ed[i].id;
        ans[id]=LCA(u,v,val);
    }
    for(int i=1; i<=cnt; ++i) {
        int I=b[ed[Kus[i]].id];
        ans[ed[Kus[i]].id]=query_min(1,dfn[I]);
    }
    for(int i=1; i<=m; ++i) {
        cout<<ans[i]<<"\n";
    }
    return 0;
}

:::