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

一、 题目分析给定一张由N个节点构成的无向图。图中包含N-1条“主要边”构成了一棵生成树另外还有M条“附加边”非树边。操作规则必须且只能切断1条主要边和1条附加边。目标求出有多少种切断方案使得整个图不再连通。在图论模型中一棵树加上若干条非树边非树边会与树上的路径形成环。如果一条主要边树边被某条附加边跨越说明这条树边位于一个环内。此时若仅切断这条树边图依然可以通过附加边连通。二、 思考过程与解题思路问题的核心转化为统计每条主要边被附加边“覆盖”了多少次。设某条主要边被覆盖的次数为k。由于我们只能再切断一条附加边因此当k0时切断这条主要边后图已经裂成两个连通块。此时第二刀切断任意一条附加边都能满足条件。方案数M。当k1时切断这条主要边后图仅靠那唯一一条覆盖它的附加边连通。因此第二刀必须且只能切断那条特定的附加边。方案数1。当k2时切断这条主要边后还有至少两条附加边维系着连通性而我们只能再切一刀无论如何也无法彻底断开。方案数0。因为树上每条边都可以用其深度较深的下端点唯一代表问题变成了给定M次操作每次将树上节点u到节点v路径上的所有边覆盖次数1最后统计每条边的覆盖次数。如果直接暴力遍历路径单次更新时间复杂度为O(N)总复杂度O(NM)必然超时。因此需要引入树上差分与最近公共祖先 (LCA)进行降维打击。三、 算法设计树上差分一种用于在树上O(1)处理路径区间加减最后O(N)统一求和得出结果的技巧。对于路径我们只需要在端点做如下标记dif[u]dif[v]dif[lca(u,v)]-2所有M条边标记完毕后跑一次自底向上的DFS回溯。节点x的真实覆盖次数cnt[x]等于其自身的差分值dif[x]加上其所有子节点y的cnt[y]之和。cnt[x] dif[x] 为了完成差分快速求解LCA成为关键。本题演示两种经典的 LCA 求解方案倍增法利用动态规划思想预处理出每个节点向上跳2^j步的祖先查询时利用二进制拆分 O(log N)逼近 LCA。RMQ法 (欧拉序ST表)通过DFS欧拉环游将树形结构展平为一维数组LCA问题转化为查询两点时间戳区间内的最小深度点。结合ST表可实现O(1)极速查询。四、 时空复杂度分析算法版本预处理时间复杂度单次查询 LCA差分与 DFS 统计总时间复杂度空间复杂度倍增法RMQ法对于本题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表的第一维均需要开到即maxn1。六、 完整代码版本一倍增求解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; vectorint 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 i1;1idepth[rt];i) fa[rt][i]fa[fa[rt][i-1]][i-1]; for(int v:vec[rt]){ //避免重复访问 if(vfaa) 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]){ vfa[v][__lg(depth[v]-depth[u])]; } //判断此时u v是否为同一个点 //如果是同一个点 代表u就是u v的最近公共祖先 if(uv) return u; //如果不是同一个点 就把u v同时向上跳 //如果会跳到同一个点就缩小步伐重新跳 for(int i__lg(depth[u]);i0;i--){ if(fa[u][i]!fa[v][i]){ ufa[u][i]; vfa[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(vfaa) continue; dfs2(v,rt); } //从叶子节点开始汇总树上差分结果 cnt[rt]dif[rt];//首先继承自身的差分标记 cnt[faa]cnt[rt]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //存图 for(int i1;in;i){ int a,b; cinab; //无向边双向加边 vec[a].push_back(b); vec[b].push_back(a); } //树可以以任何节点作为根节点 //所以假设一号节点为根节点 根节点没有父节点 所以设置为0 //通过dfs得到深度数组和倍增数组 dfs(1,0); //接下来通过树上差分来存附加边 for(int i1;im;i){ int a,b; cinab; dif[a]; dif[b]; dif[lca(a,b)]-2; } //通过dfs 汇总差分数组 dfs2(1,0); //最后计算总方案数 //通过查看每个点和它的父节点之间有几条附加边 //如果1条都没有 方案数m //如果有一条 方案数1 //如果大于一条 方案数0 //1号节点作为根结点 没有父节点 所以从2号节点开始计算 for(int i2;in;i){ if(cnt[i]0) ansm; else if(cnt[i]1) ans; } coutans; return 0; }版本二RMQ欧拉环游ST表结合树上差分//第二种方法rmq求lca #include iostream #include vector #include algorithm using namespace std; const int maxn100010; int n,m; //欧拉环游过程中经过的所有点 e[i]是环游过程中第i个访问到的节点 int e[maxn1]; int l[maxn1];//欧拉环游过程中经过的所有点对应的深度e表对应 int h[maxn1];//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[maxn1][20]; long long ans;//记录总方案数 vectorint 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(vfa) continue; dfs(v,rt); //回溯 记录经过当前节点 e[cnt1]rt; //记录当前节点深度为上一个节点深度-1 //因为回溯 所以上一个节点是当前节点儿子 l[cnt1]l[cnt1-1]-1; } } //预处理生成关于l深度的st表 void pre(){ //以i为起点 区间长度为1的区间内 最小值的下标是i for(int i1;i2*n-1;i) st[i][0]i; //外层循环枚举区间长度的指数 for(int j1;1j2*n-1;j){ int tmp1(j-1); //内层循环枚举区间起点 确保区间不越界 for(int i1;i(1j)-12*n-1;i){ if(l[st[i][j-1]]l[st[itmp][j-1]]) st[i][j]st[i][j-1]; else st[i][j]st[itmp][j-1]; } } } //查询u和v的最近公共祖先 int lca(int u,int v){ //确保v永远是u v中较大的那一个 方便后面计算 if(vu) swap(u,v); int k__lg(v-u1); int tmp1k; if(l[st[u][k]]l[st[v-tmp1][k]]) return e[st[u][k]]; else return e[st[v-tmp1][k]]; } //rt为当前节点 fa为当前节点的父节点 void dfs2(int rt,int faa){ //先递归到叶子节点 for(int v:vec[rt]){ //避免重复访问 if(vfaa) continue; dfs2(v,rt); } //从叶子节点开始汇总树上差分结果 cnt[rt]dif[rt]; cnt[faa]cnt[rt]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //存图主要边 for(int i1;in;i){ int a,b; cinab; vec[a].push_back(b); vec[b].push_back(a); } //对树进行欧拉环游 生成e l h数组 //假设1号节点为根节点 根节点没有父节点 虚拟为0 dfs(1,0); //预处理生成关于l深度的st表 pre(); //接下来存附加边 for(int i1;im;i){ int a,b; cinab; 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 i2;in;i){ if(cnt[i]0) ansm; else if(cnt[i]1) ans; } coutans; return 0; }