【例 2】暗的连锁（信息学奥赛一本通- P1553）

罗湖老棍子

141人浏览 · 2026-10-21 14:30:00

罗湖老棍子 · 2026-10-21 14:30:00 发布

一、题目分析

给定一张由N个节点构成的无向图。图中包含N-1条“主要边”构成了一棵生成树，另外还有M条“附加边”（非树边）。

操作规则：必须且只能切断1条主要边和1条附加边。

目标：求出有多少种切断方案，使得整个图不再连通。

在图论模型中，一棵树加上若干条非树边，非树边会与树上的路径形成环。如果一条主要边（树边）被某条附加边跨越，说明这条树边位于一个环内。此时若仅切断这条树边，图依然可以通过附加边连通。

二、思考过程与解题思路

问题的核心转化为：统计每条主要边被附加边“覆盖”了多少次。

设某条主要边被覆盖的次数为k。由于我们只能再切断一条附加边，因此：

当k=0时：切断这条主要边后，图已经裂成两个连通块。此时第二刀切断任意一条附加边都能满足条件。方案数+M。
当k=1时：切断这条主要边后，图仅靠那唯一一条覆盖它的附加边连通。因此第二刀必须且只能切断那条特定的附加边。方案数+1。
当k>=2时：切断这条主要边后，还有至少两条附加边维系着连通性，而我们只能再切一刀，无论如何也无法彻底断开。方案数+0。

因为树上每条边都可以用其深度较深的下端点唯一代表，问题变成了：给定M次操作，每次将树上节点u到节点v路径上的所有边覆盖次数+1，最后统计每条边的覆盖次数。

如果直接暴力遍历路径，单次更新时间复杂度为O(N)，总复杂度O(NM)必然超时。因此，需要引入树上差分与最近公共祖先 (LCA) 进行降维打击。

三、算法设计

树上差分：

一种用于在树上O(1)处理路径区间加减，最后O(N)统一求和得出结果的技巧。

对于路径 $u \to v$ ，我们只需要在端点做如下标记：

dif[u]++
dif[v]++
dif[lca(u,v)]-=2

所有M条边标记完毕后，跑一次自底向上的DFS回溯。节点x的真实覆盖次数cnt[x]等于其自身的差分值dif[x]加上其所有子节点y的cnt[y]之和。

cnt[x] = dif[x] + $\sum_{y \in child(x)} cnt[y]$

为了完成差分，快速求解LCA成为关键。本题演示两种经典的 LCA 求解方案：

倍增法：利用动态规划思想预处理出每个节点向上跳2^j步的祖先，查询时利用二进制拆分 O(log N)逼近 LCA。
RMQ法 (欧拉序+ST表)：通过DFS欧拉环游将树形结构展平为一维数组，LCA问题转化为查询两点时间戳区间内的最小深度点。结合ST表可实现O(1)极速查询。

四、时空复杂度分析

算法版本	预处理时间复杂度	单次查询 LCA	差分与 DFS 统计	总时间复杂度	空间复杂度
倍增法	$O(N \log N)$	$O(\log N)$	$O(N)$	$O((N + M) \log N)$	$O(N \log N)$
RMQ法	$O(N \log N)$	$O(1)$	$O(N)$	$O(N \log N + M)$	$O(N \log N)$

对于本题10^5的数据规模，两种方法均能毫无压力地满分通过。RMQ法在查询密集的场景（M极大时）常数更优。

五、坑点总结

附加边的本质跨度：附加边连接的绝非仅是相邻节点。一条跨越整棵树的附加边会保护沿途所有的主要边，切忌使用哈希表（如map）仅统计相邻节点的边。
根节点的边界特判：在统计答案时，cnt[i]代表的是节点i与其父节点之间的连边。假设指定1号节点为树根，那么根节点之上是不存在主要边的，循环统计答案时必须从2开始（即忽略cnt[1]）。
RMQ查询的参数陷阱：在使用ST表查LCA时，传入的参数绝对不能是树上节点编号a和b，必须是它们在欧拉序中第一次出现的时间戳（下标），即h[a]和h[b]。
欧拉序列的数组容量：一次欧拉环游包含所有“下探”和“回溯”，生成的序列长度为2N-1。因此，对应的节点数组e、深度数组l以及ST表的第一维，均需要开到 $2 \times 10^5$ （即 maxn<<1）。

六、完整代码

版本一：倍增求解LCA结合树上差分

//这道题因为附加边题目给出的附加边是可以跨越连接任意两个节点的
//所以如果在节点1和节点10之间连一条附加边
//那么从1到10的整条树上路径 都会被这条附加边连接起来
//所以不能用简单的存边去做 需要使用树上差分
//这道题根据题目可知 有n-1条主要边 且任意两个节点之间都存在一条由主要边构成的路径
//所以这是一颗树 且根据树的性质 每个节点与父节点之间只有一条边
//即a b之间如果有一条附加边 那么dif[a]++ dif[b]++
//dif[lca(a,b)]-2 
//最后所有附加边都遍历完后
//一趟dfs即可求出每个点与与父节点之间有多少条附加边
//第一种方法倍增求lca
#include <iostream>
#include <vector>
using namespace std;
vector<int> vec[100010];//邻接表
int n,m;
int depth[100010];//depth[i]代表i节点的深度
int fa[100010][20];//fa[i][j]代表i节点向上走2^j步所处的节点
long long ans;//记录总方案数
int dif[100010];//树上差分标记数组 

//cnt[i]代表i和它的父节点之间有几条附加边
//其实这里不开cnt 直接中间数组dif汇总也可以 
//但为了方便同学们理解 我拆开来
int cnt[100010];//差分数组最后通过dfs生成的最终数组 

//rt为当前节点 faa为当前节点的父节点
void dfs(int rt,int faa){
    //当前节点的深度是父节点+1
    depth[rt]=depth[faa]+1;
    //当前节点向上一步是父节点
    fa[rt][0]=faa;

    for(int i=1;1<<i<=depth[rt];i++)
        fa[rt][i]=fa[fa[rt][i-1]][i-1];

    for(int v:vec[rt]){
        //避免重复访问
        if(v==faa) continue;
        dfs(v,rt);
    }
}

//求u v的最近公共祖先
int lca(int u,int v){
    //确保v永远是u v中深度较深的那一个
    if(depth[v]<depth[u]) swap(u,v);
    //然后先把v上升到和u同一深度
    while(depth[v]!=depth[u]){
        v=fa[v][__lg(depth[v]-depth[u])];
    }

    //判断此时u v是否为同一个点
    //如果是同一个点 代表u就是u v的最近公共祖先
    if(u==v) return u;

    //如果不是同一个点 就把u v同时向上跳
    //如果会跳到同一个点就缩小步伐重新跳
    for(int i=__lg(depth[u]);i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    //最后u和v会停留在lca(u,v)正下方
    return fa[u][0];
}

//rt为当前节点 fa为当前节点的父节点
void dfs2(int rt,int faa){
    //先递归到叶子节点
    for(int v:vec[rt]){
        //避免重复访问
        if(v==faa) continue;
        dfs2(v,rt);
    }
    //从叶子节点开始汇总树上差分结果
    cnt[rt]+=dif[rt];//首先继承自身的差分标记
    cnt[faa]+=cnt[rt];
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    //存图
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        //无向边双向加边
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    //树可以以任何节点作为根节点
    //所以假设一号节点为根节点 根节点没有父节点 所以设置为0
    //通过dfs得到深度数组和倍增数组
    dfs(1,0);
    //接下来通过树上差分来存附加边
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        dif[a]++;
        dif[b]++;
        dif[lca(a,b)]-=2;
    }
    //通过dfs 汇总差分数组
    dfs2(1,0);
    
    //最后计算总方案数
    //通过查看每个点和它的父节点之间有几条附加边
    //如果1条都没有 方案数+m
    //如果有一条 方案数+1；
    //如果大于一条 方案数+0
    //1号节点作为根结点 没有父节点 所以从2号节点开始计算
    for(int i=2;i<=n;i++){
        if(cnt[i]==0) ans+=m;
        else if(cnt[i]==1) ans++;
    }
    cout<<ans;
    return 0;
}

版本二：RMQ（欧拉环游+ST表）结合树上差分

//第二种方法rmq求lca
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=100010;
int n,m;

//欧拉环游过程中经过的所有点 e[i]是环游过程中第i个访问到的节点
int e[maxn<<1];
int l[maxn<<1];//欧拉环游过程中经过的所有点对应的深度（e表对应）
int h[maxn<<1];//h[i]代表e表中节点i第一次出现的下标
int cnt1;
int dif[maxn];//差分数组 

//cnt[i]代表i和它的父节点之间有几条附加边
//其实这里不开cnt 直接中间数组dif汇总也可以 
//但为了方便同学们理解 我拆开来
int cnt[maxn];//差分数组最后通过dfs生成的最终数组 
//st[i][j]代表以i为起点 长度为2^j的区间内的最小值的下标
int st[maxn<<1][20];
long long ans;//记录总方案数
vector<int> vec[maxn];//邻接表

//欧拉环游生成e l h表
//rt为当前节点 fa为当前节点父节点
void dfs(int rt,int fa){
    //记录经过当前节点
    e[++cnt1]=rt;
    //当前当前节点深度为父节点深度+1
    l[cnt1]=l[cnt1-1]+1;
    //记录e表中rt节点第一次出现的下标是cnt
    h[rt]=cnt1;

    for(int v:vec[rt]){
        //避免重复访问
        if(v==fa) continue;
        dfs(v,rt);
        //回溯 记录经过当前节点
        e[++cnt1]=rt;
        //记录当前节点深度为上一个节点深度-1
        //因为回溯 所以上一个节点是当前节点儿子
        l[cnt1]=l[cnt1-1]-1;
    }
}

//预处理生成关于l（深度）的st表
void pre(){
    //以i为起点 区间长度为1的区间内 最小值的下标是i
    for(int i=1;i<=2*n-1;i++) st[i][0]=i;

    //外层循环枚举区间长度的指数
    for(int j=1;1<<j<=2*n-1;j++){
        int tmp=1<<(j-1);
        //内层循环枚举区间起点 确保区间不越界
        for(int i=1;i+(1<<j)-1<=2*n-1;i++){
            if(l[st[i][j-1]]<l[st[i+tmp][j-1]])
                st[i][j]=st[i][j-1];
            else st[i][j]=st[i+tmp][j-1];
        }
    }
}

//查询u和v的最近公共祖先
int lca(int u,int v){
    //确保v永远是u v中较大的那一个 方便后面计算
    if(v<u) swap(u,v);
    int k=__lg(v-u+1);
    int tmp=1<<k;
    if(l[st[u][k]]<l[st[v-tmp+1][k]]) return e[st[u][k]];
    else return e[st[v-tmp+1][k]];
}

//rt为当前节点 fa为当前节点的父节点
void dfs2(int rt,int faa){
    //先递归到叶子节点
    for(int v:vec[rt]){
        //避免重复访问
        if(v==faa) continue;
        dfs2(v,rt);
    }
    //从叶子节点开始汇总树上差分结果
    cnt[rt]+=dif[rt];
    cnt[faa]+=cnt[rt];
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    //存图（主要边）
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    //对树进行欧拉环游 生成e l h数组
    //假设1号节点为根节点 根节点没有父节点 虚拟为0
    dfs(1,0);

    //预处理生成关于l（深度）的st表
    pre();

    //接下来存附加边
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        dif[a]++;
        dif[b]++;
        //a和b的最近公共祖先就是l表中a第一次出现的位置和b第一次出现的位置
        //的区间内l最小的下标在e表中所对应的点
        dif[lca(h[a],h[b])]-=2;
    }
    //通过dfs汇总差分数组
    dfs2(1,0);
    //最多计算总方案数
    //1号节点作为根结点 不存在父节点
    for(int i=2;i<=n;i++){
        if(cnt[i]==0) ans+=m;
        else if(cnt[i]==1) ans++;
    }
    cout<<ans;
    return 0;
}