[Solution] [COCI 2023/2024 #1] Mostovi

cherry2010 · 2026-01-22 19:10:47 · 题解

Solution

一个唯一优势大概只有想法可能较为自然的做法。

先观察部分分，m-n\le 20 提示性很强：如果放在生成树上，则说明非树边数量 \le 21；加之这是一个在图上没什么思路的问题，于是自然想到建出图的生成树。而对生成树计数考虑将树边和非树边分开处理。

注意，在整道题目中，通过 DFS 序生成树中所有返祖边为祖孙关系这个结论简化了很多分讨。

树边

一条树边 (x,y) 的删除会将整棵树划分成几个区域：x 子树外、x 其余子树、y 子树。其中 x 可能为根而不存在第一个区域，故考虑对 x 是否为根分讨。注意其他两个区域也可能不存在，但是在分讨后会发现可以被情况包含，这里跳过多余的情况。

当 x 为根时，形如：
- 强烈建议画图时画出多个子树，否则很容易漏情况。
- 设 rd_x 表示 x 的树边度数。因为 x,y 其余子树并非祖孙关系，所以在其之间不可能存在返祖边。
- 容易得出当 rd_x+rd_y>3 时，新图不连通。
当 x 不为根时，形如：
- 如图，蓝色虚线为可能的非树边情况。容易发现当且仅当 x 除开 y 方向的所有子树和 y 所有子树都有连向 x 子树外连通块的返祖边时新图联通。显然向上的返祖边端点深度越小越可能使得联通，考虑记录 mn_x 表示子树内最浅返祖边端点的深度。而因为所有点都需要满足 mn_x<d_x，于是设 mx_x=\max_{(x,y)\in E}mn_y，当 mx_x\ge d_x 时说明不存在合法返祖边，新图不连通。需要处理去除一个子节点方向的子树的情况，记录 smx_x 表示 mn 次大值即可，可以得出 pmx_{x,y} 表示 x 去除 y 方向子树后的 mx_x。
- 则当 mx_y\ge d_x 或 pmx_{x,y}\ge d_x 时，新图不连通。注意判断 x,y 子树是否存在。

非树边

形如：

画得有点花，这里解释一下。当前处理的是非树边 (x,y)，除开 x,y 的所有点分成了 4 个可能的区域（绿色框圈出），蓝色虚线为区域之间可能的非树边情况，son_y 表示 y 在 x 方向的子节点。考虑分讨 4 个区域的存在情况计数。

不存在 1,4 区域。
- 如图，显然当 y 存在多个子树，即 rd_y>1 时，新图不连通。
不存在 1 区域。
- 首先当 rd_y>1 时 2 区域不可能和其它区域联通，新图不连通。
- 考虑如何判断 4 区域中所有子树连通块是否都有连向 3 区域的返祖边。因为需要所有子树都有连边，可以分别对每个子树有连边的深度区间打标记，所查询的深度区间标记数等于子树数则合法。因此我们在处理 x 所有向上的返祖边前预处理其所有子树。对一个子树 z，如果存在其子树中连至 x 祖先的返祖边在深度 d 下方，则 d 的下方标记数 D_d\leftarrow D_d+1；同理，如果存在返祖边在 d 上方，则 d 的上方标记数 U_d\leftarrow U_d+1。设 d_1,d_2 表示 z 连至 x 祖先的返祖边的最浅/最深的端点，则 d>d_1 的 U_d\leftarrow U_d+1，d<d_2 的 D_d\leftarrow D_d+1。D,U 可以使用树状数组维护。
- 当前情况其实不需要上方标记数。当 D_y<rd_x-1 时，说明存在 x 的子树不存在端点在 [d_y+1,d_x-1] 深度范围内的返祖边，新图不连通。
不存在 4 区域。
- 判断 1,2 区域是否联通和树边情况且 x 不为根时相同。
- 考虑如何判断 son_y 子树中去除 x 点的返祖边后是否仍存在返祖边连向 1 区域。祖先除去子树信息，考虑可持久化线段树维护。具体地，在 x 的可持久化线段树中维护 x 子树中不同深度作为返祖边端点的数量。这颗可持久化线段树同时还可以二分查找到前面所需的 d_1,d_2。
存在 1,4 区域。
- 先判断 1,2 区域是否联通。
- 此时可能通过 1,4 和 3,4 区域的连边使得 1,3 区域联通，这使得判断是否联通显得很麻烦。但是可以发现，1,3,4 区域中原本有 rd_x+1 个连通块，如果最终全部联通，则所有连通块度数不为 0，且至少存在 rd_x 个不重合的块间非树边，也即可以形成一棵树。因此计算 rd_x+1 个连通块之间不重合的非树边的数量，如果 < rd_x 则说明无法形成一棵树，新图不连通。于是转为了计数问题，其中 1,4 区域之间边数为 U_y，3,4 区域之间边数为 D_y，3,4 区域是否联通可以用可持久化线段树判断。
其他情况。
- 和树边的分讨一样，可以发现已经包含在分讨中了，不需要再处理。

注意在处理 d_1,d_2 时可能的特殊情况：

当 d_1=d_2=0 时，当前子树不可能和任意一个其余区域联通，而 3 区域必然存在，因此删去任意以 x 为端点的非树边，新图不连通。
当 d_1=d_2 时，在删去的非树边另一端点有 d_y=d_1=d_2 时，当前子树出现和 d_1=d_2=0 一样的情况，新图不连通。因此对符合条件的 d_1=d_2 打标记即可。

时间复杂度 O(m\log n)。

可能有更简单的判断方法，但考场上做得太红温了，只想到了这几个较为无脑的做法。

Code

看着有点长，但实际上核心计数分讨部分非常短，大部分码量在预处理，比如主席树板子就占了很大的篇幅。分讨完全、思路清晰之后写出来很快。

#include <bits/stdc++.h>
using namespace std;

char BEGIN;
namespace Cherry {
    const int N=1e5+10,M=3e5+10;
    int n,m,ans;
    int d[N],siz[N],rd[N],son[N],edf[N];
    int mn[N],mx[N],mx2[N];
    int Mn[N],Mx[N];
    bool vis[N];

    struct SegmentTree {
        int cnt;
        int rt[N];
        struct tree {
            int ls,rs,cnt;
        }tr[70*N];
        int new_node(int id) { return tr[++cnt]=tr[id],cnt; }
        void pushup(int id) { tr[id].cnt=tr[tr[id].ls].cnt+tr[tr[id].rs].cnt; }
        void modify(int &id,int l,int r,int x,int d) {
            id=new_node(id);
            if(l==r) return tr[id].cnt+=d,void();
            int mid=(l+r)/2;
            if(x<=mid) modify(tr[id].ls,l,mid,x,d);
            else modify(tr[id].rs,mid+1,r,x,d);
            pushup(id);
        }
        int merge(int x,int y,int l,int r) {
            if(!x||!y) return x|y;
            int id=++cnt;
            tr[id].cnt=tr[x].cnt+tr[y].cnt;
            if(l==r) return id;
            int mid=(l+r)/2;
            tr[id].ls=merge(tr[x].ls,tr[y].ls,l,mid);
            tr[id].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
            pushup(id);
            return id;
        }
        int query(int id1,int id2,int l,int r,int lt,int rt) {
            if(!id1&&!id2) return 0;
            if(l>=lt&&r<=rt) return tr[id2].cnt-tr[id1].cnt;
            int mid=(l+r)/2;
            if(lt<=mid&&query(tr[id1].ls,tr[id2].ls,l,mid,lt,rt)) return 1;
            if(rt>mid&&query(tr[id1].rs,tr[id2].rs,mid+1,r,lt,rt)) return 1;
            return 0;
        }
        int findl(int id,int l,int r,int lt,int rt) {
            if(!id||!tr[id].cnt) return 0;
            if(l==r) return l;
            int mid=(l+r)/2;
            if(rt<=mid) return findl(tr[id].ls,l,mid,lt,rt);
            if(tr[tr[id].ls].cnt) return findl(tr[id].ls,l,mid,lt,rt);
            return findl(tr[id].rs,mid+1,r,lt,rt);
        }
        int findr(int id,int l,int r,int lt,int rt) {
            if(!id||!tr[id].cnt) return 0;
            if(l==r) return l;
            int mid=(l+r)/2;
            if(rt<=mid) return findr(tr[id].ls,l,mid,lt,rt);
            int x=findr(tr[id].rs,mid+1,r,lt,rt);
            if(!x) x=findr(tr[id].ls,l,mid,lt,rt);
            return x;
        }
    }T;
    bool check(int x,int y,int d1,int d2) { return T.query(T.rt[y],T.rt[x],1,n,d1,d2); } //判断 x 子树除去 y 后在 [d1,d2] 深度中是否有连边

    struct edge {
        int y,f,nextt;
    }e[2*M];
    int tot;
    int elast[N];
    void add(int x,int y) {
        e[++tot].y=y;
        e[tot].nextt=elast[x];
        elast[x]=tot;
    }

    void dfs(int x,int fa) {
        d[x]=d[fa]+1,siz[x]=1,mn[x]=n+1;
        for(int i=elast[x];i;i=e[i].nextt) {
            int y=e[i].y;
            if(y==fa) continue;
            if(!d[y]) {
                rd[x]++,rd[y]++,e[i].f=1;
                dfs(y,x);
                siz[x]+=siz[y];
                mn[x]=min(mn[x],mn[y]); //子树中连到最上方的非树边端点
                if(mn[y]>mx[x]) mx2[x]=mx[x],mx[x]=mn[y]; //子树 mn 最大次大值
                else if(mn[y]>mx2[x]) mx2[x]=mn[y];
            }
            else mn[x]=min(mn[x],d[y]);
            if(d[x]>d[y]) edf[x]++;
        }
    }
    void dfs2(int x,int fa) { //主席树维护子树内非树边端点
        for(int i=elast[x];i;i=e[i].nextt) {
            if(!e[i].f) continue;
            int y=e[i].y;
            dfs2(y,x);
            T.rt[x]=T.merge(T.rt[x],T.rt[y],1,n);
        }
        for(int i=elast[x];i;i=e[i].nextt) {
            int y=e[i].y;
            if(y==fa||e[i].f||d[x]<d[y]) continue;
            T.modify(T.rt[x],1,n,d[y],1);
        }
    }

    int get(int x,int y) { return (mn[y]!=mx[x]?mx[x]:mx2[x]); } //x 除开 y 方向的子节点中子树最浅非树边端点的最深深度
    void solve1(int x) { //树边
        for(int i=elast[x];i;i=e[i].nextt) {
            if(!e[i].f) continue;
            int y=e[i].y;
            if(x!=1) {
                if(siz[y]>1&&mx[y]>=d[x]) ans++; //y 子树无法连接 x 上方的连通块
                else if(siz[x]>siz[y]+1&&get(x,y)>=d[x]) ans++; //其余子节点无法连接 x 上方的连通块
            }
            else if(x==1&&rd[x]+rd[y]>3) ans++;
            solve1(y);
        }
    }

    struct BIT1 {
        int tr[N];
        int lowbit(int x) { return x&-x; }
        void add(int x,int d) { for(int i=n-x+1;i<=n;i+=lowbit(i)) tr[i]+=d; }
        int query(int x,int res=0) {
            for(int i=n-x+1;i>=1;i-=lowbit(i)) res+=tr[i];
            return res;
        }
    }Td;
    struct BIT2 {
        int tr[N];
        int lowbit(int x) { return x&-x; }
        void add(int x,int d) { for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=d; }
        int query(int x,int res=0) {
            for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];
            return res;
        }
    }Tu;

    void solve2(int x,int fa) { //非树边
        for(int i=elast[x];i;i=e[i].nextt) {
            if(!e[i].f) continue;
            son[x]=e[i].y;
            solve2(e[i].y,x);
        }
        if(!edf[x]) return;
        bool flag=0;
        for(int i=elast[x];i;i=e[i].nextt) { //判断 x 不同子树向上非树边情况
            if(!e[i].f) continue;
            int y=e[i].y;
            Mn[y]=T.findl(T.rt[y],1,n,1,d[x]-1); //最浅和最深的端点
            Mx[y]=T.findr(T.rt[y],1,n,1,d[x]-1);
            if(!Mn[y]) flag=1;
            else Td.add(Mx[y]-1,1),Tu.add(Mn[y]+1,1); //Td/Tu 维护若删除的是深度 d 的点，则有多少 x 的子树在 d 上/下方有连边
            if(Mn[y]==Mx[y]) vis[Mn[y]]=1; //注意特判子树内只有一条连接 x 上方的非树边的情况
        }
        for(int i=elast[x];i;i=e[i].nextt) {
            int y=e[i].y;
            if(y==fa||e[i].f||d[x]<d[y]) continue;
            if(flag) ans++;
            else if(vis[d[y]]) ans++;
            else if(n==siz[y]&&siz[x]==1) {
                if(rd[y]>1) ans++;
            }
            else if(n==siz[y]) {
                if(rd[y]>1||Td.query(d[y])<rd[x]-1) ans++;
            }
            else if(siz[x]==1) {
                if(!check(son[y],x,1,d[y]-1)||(rd[y]>2&&get(y,son[y])>=d[y])) ans++;
            }
            else {
                if(rd[y]>2&&get(y,son[y])>=d[y]) ans++;
                else if(check(son[y],x,1,d[y]-1)+Td.query(d[y])+Tu.query(d[y])<rd[x]) ans++; //边数 >=rd[x] 且所有连通块 rd!=0 -> rd[x]+1 个联通块联通
            }
        }
        for(int i=elast[x];i;i=e[i].nextt) {
            if(!e[i].f) continue;
            int y=e[i].y;
            if(Mn[y]) Td.add(Mx[y]-1,-1),Tu.add(Mn[y]+1,-1);
            vis[Mn[y]]=0;
        }
    }

    int main() {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++) {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y),add(y,x);
        }
        dfs(1,0),dfs2(1,0),solve1(1),solve2(1,0);
        printf("%d",ans);

        return 0;
    }
}
char END;

int main() {
//    freopen("bridge.in","r",stdin);
//    freopen("bridge.out","w",stdout);
    clock_t begin=clock();
    Cherry::main();
    clock_t end=clock();
    fprintf(stderr,"Time: %.3lf/1 s\n",(end-begin)/1000.0);
    fprintf(stderr,"Memory: %.3lf/512 MB\n",abs(&BEGIN-&END)/1024.0/1024.0);

    return 0;
}
//g++ bridge.cpp -o bridge -std=c++14 -Wall -O2 "-Wl,--stack=2000000000"

附赠一些小样例：