看到“闇の連鎖”这个标题我第一反应是哪个番的剧情直到打开题面才发现这是经典的树上差分模型题考察的就是边差分 dfs预处理这套组合拳。题目结构很简洁——n 个点n-1 条主边构成一棵树另外再给 m 条附加边。问的是同时砍掉一条主边和一条附加边有多少种方案能让整棵树变成两个互不连通的部分。第一次做这题的人十有八九会从“枚举第一刀、再枚举第二刀”往下钻然后被数据范围劝退。这篇文章就把这道题从题意建模、边差分原理、dfs预处理到最终统计答案完整拆一遍适合正在刷 LCA 和树上差分的选手参考也适合想搞懂“为什么三个标记就能代替一整条路径暴力加一”的新手。1. 先把“闇の連鎖”的题意翻译成“切两条边”1.1 树边加附加边砍一刀已经不够了先说我第一次见到这题时的直觉既然有 n-1 条主边树本来就是连通的随便删一条主边似乎就应该分成两块。但题目偏要你“再删一条附加边”这个附加条件才是关键。主边被删掉之后如果恰好有一条附加边跨过这条主边的两侧那么两个小连通块还能通过这条路重新连起来树并没有真正分裂。这也是题目名字里“連鎖”的意味附加边就像是给树上了额外锁链一条链不够得把锁链也剪断。所以题意要重新翻译一下我们要找的其实是“一对边”其中第一条必须是主边第二条必须是附加边删除它们之后整张图的连通分量数从 1 变成 2。这里有个很容易被忽略的细节附加边并不是可以随便乱删的普通边它本质上是“非树边”不会成为新的必须删的点但同时它也不能单独断开树。理解了这一点再看后面差分算法的目标就顺了我们只关心主边被“多少条附加边跨过”也就是每条主边的附加边覆盖次数。1.2 朴素枚举为什么必然超时假设 n 和 m 都在 1e5 的规模。直接枚举主边和附加边的配对就有 O(nm) 种方案大约是 1e10哪怕每次判断连通性只花常数时间都完全不能接受如果每次再暴力跑一遍 DFS 或者并查集判连通复杂度还要再乘一个 n那基本是天文数字。因此正确思路不是枚举“两把刀”而是只枚举第一把刀先想清楚删掉一条主边之后树会裂成什么样再来回答“第二把刀选哪些附加边能真正断开”。这样枚举范围从 O(nm) 降到了 O(n)剩下要解决的是“快速知道每条主边被多少条附加边覆盖”。这个数量就是我们说的覆盖次数 cnt[e]它是后面所有统计的地基。说白了这是一道“先静态统计、再分类计数”的题暴力动态判连通是南辕北辙。1.3 方案数的真正含义每条主边的“连桥责任”设主边 e 被 cnt[e] 条附加边跨过。删掉 e 后树的左右两侧之间如果有额外连接一定是那些跨过 e 的附加边。于是分三种情况cnt[e] 0e 本身就是桥。删掉它树已经分裂第二把刀附加边随便选哪条都行方案贡献 m。cnt[e] 1只有那一条跨过 e 的附加边连接左右。必须连它也删掉树才真正变成两块贡献 1。cnt[e] 2至少还有两条“残余桥梁”。只删一条附加边并不能断开贡献 0。把所有主边的贡献加起来就是答案。整个问题瞬时变成一个单纯的树上统计问题给 m 条附加边每条都在树上对应一条简单路径 u - v我需要对这条路径上的所有边覆盖次数 1最后查每条边被加了几次。暴力做会超时于是来到今天的重头戏边差分。2. 边差分标记的原理三个 O(1) 更新搞定一条路径2.1 从“路径上暴力 1”到“端点打标记”的直觉转换先回顾一维差分的思路对数组 a 的区间 [l, r] 每个位置 1不需要真的循环只需要 d[l] 1d[r1] - 1最后做前缀和还原。树上差分本质是同一思想搬到树结构上只是“前缀和”变成了“从叶子到根的累加”。在树上任何一条简单路径 u - v 都可以看成两部分u 往上到 lcav 往上到 lca。如果我们想给“u 到根路径上的所有边”1做法很简单标记 d[u] 1 就完事因为回溯累加时这个 1 会一路上传覆盖 u 到根的每一条边。同理给“v 到根路径上的所有边”1就标记 d[v] 1。但 u - v 路径是两段往上爬的路径不能包括 lca 上面的公共部分我们需要在 lca 处把上溢的标记扣掉这正是 -2 的来源。2.2 为什么 lca 处是 -2 而不是 -1这是边差分新手最容易卡住的地方我也曾经在这里翻过车。先看点差分如果给路径 u-v 上的“节点权值”1标记是 d[u], d[v], d[lca]--, d[fa[lca]]--。因为 lca 这个点本身要被 1 一次而且从 lca 到根的公共段会被两个端点同时累加所以要用两个 -1 分别扣除。但边差分不同。树上每条边都“下沉”到它深度更大的那个子节点也就是说我们在统计环节用 cnt[child] 来表示“父节点到该子节点的那条边”。对路径 u-v它的边集包括 u 到 lca 路径上所有子节点对应的边、v 到 lca 路径上所有子节点对应的边但绝对不包括 lca 自己对应的边lca 到父节点的边不在这条路径上。如果 lca 处只减 1回溯时 lca 上面还会残留重复计数只有减 2 才能让公共段恰好抵消为 0。用手推一个最小例子链 1 - 2 - 3附加边是 3 - 1。lca(3,1)1标记为 d[3], d[1], d[1]-2即 d[3]1, d[1]-1。后序累加cnt[3]1cnt[2]cnt[3]d[2]1cnt[1]d[1]cnt[2]0。cnt[3] 表示边 2-3 被覆盖 1 次cnt[2] 表示边 1-2 被覆盖 1 次cnt[1] 没有对应父边结果为 0完全正确。如果当初写成 -1结果会多出一些不该有的覆盖。多说一句代码里的 diff[l] - 2 一定要和以后会遇到的点差分区分开这是我在给朋友讲题时最常提醒的一个位置。2.3 后序回溯累加把标记还原成每条边的覆盖次数标记打完之后还需要一次 DFS 把所有标记“兑现”成真实覆盖次数。顺序必须是后序先递归完所有子树再处理当前节点。伪代码逻辑cnt[u] diff[u]; for v in children(u): dfs(v); cnt[u] cnt[v];为什么不能先序因为一个节点的 cnt 依赖所有孩子的 cnt而孩子的 cnt 又依赖他们的孩子必须自底向上才能把端点上的 1 一点一点推向根部。执行完之后cnt[u] 就是“节点 u 和它父亲之间那条主边”的附加边覆盖次数。这里同步强调一个关键点根节点没有父边所以根节点的 cnt 不参与答案统计后面代码里会专门处理。3. dfs 预处理三件套深度、倍增 LCA、差分数组布局3.1 一次 dfs 建树能顺手拿到什么整道题的第一步是 dfs 预处理目的就一个让后续任意两个节点的 LCA 查询都能在 O(log n) 内完成。第一次 dfs 从根我习惯用 1 号点出发会顺手拿到三样东西depth[u]节点深度用于把 u、v 对齐到同一层。up[0][u]u 的父节点是倍增表的第 0 层。up[k][u] up[k-1][up[k-1][u]]u 往上跳 2^k 步到达的点。因为树本身是无环的遍历时只需要判断“v fa”就能防止走回头路不需要额外的 vis 数组。这部分代码很短但有个顺序问题值得单独拿出来说。3.2 倍增 LCA 查询的书写细节与边界LCA 查询分两步。第一步若 depth[a] depth[b] 则交换保证 a 更深然后按照深度差 d 的二进制位把 a 往上跳到和 b 同层。第二步从 k LOG-1 开始往下枚举只要 up[k][a] ! up[k][b]就让 a 和 b 同时往上跳。这个“从大到小”的顺序很关键如果从小到大跳很容易跳过 LCA跳到 LCA 的祖先上去后面就全乱了。循环结束后 a 和 b 的儿子刚好在 LCA 的下方所以返回 up[0][a] 即可。边界情况也要想清楚如果一开始 a 就是 b 的祖先那么第一步对齐后 a b直接返回 a如果 u vLCA 就是它自己。这些情况在差分标记里都不会出问题因为 diff[lca] - 2 依旧成立只是路径退化成单点最终覆盖次数为 0不影响答案。3.3 预处理顺序决定正确性先建 up 表再递归子树我见过不少同学的代码把递归子树的逻辑放在倍增表填充之前写成了这样depth[v] depth[u] 1; dfs_pre(v, u); up[k][v] ...这样看起来好像也没差但一旦查询 LCA 的时候访问到尚未填充的 up[k][v]就会读出未初始化值轻则 TLE重则答案完全错乱。正确顺序是进入 dfs_pre(u, fa) 后立即设置 up[0][u] fa用循环把整行 up[k][u] 全部填好然后再遍历孩子递归。深度也是先算好再传下去。原因是子节点在递归里可能立刻要用父节点的整张 up 表而父节点的表是“先有父才有子”的。另外提醒一句深链数据比如一条 2e5 的直线在严格评测环境里有可能把递归栈逼爆。大多数题解直接递归也能过但如果你遇到栈溢出可以先把递归版写好验证逻辑再把它改成显式栈的迭代版或者用某些编译指令扩栈这个看个人习惯了。4. 统计答案的三种分支与完整代码实现4.1 cnt0、cnt1、cnt2 分别对应几次有效切割其实在 1.3 已经推导过结论这里再从实现角度重述一遍对每一条主边也就是对根节点之外的所有节点 u检查 cnt[u] 的值。条件含义附加边选择方案贡献cnt[u] 0该主边是桥m 条附加边任选其一mcnt[u] 1唯一一条附加边跨过它必须选那条附加边1cnt[u] 2至少两条附加边跨过它选任一条都不够断开0为什么 cnt0 时附加边可以任意选因为删掉主边后树已经分裂再删的附加边无论连接的是左块内部还是右块内部都不会再把两块接回去。这里不要带普通图的直觉——附加边再多它们也不参与主干连接只要主桥断开整图必裂。cnt 统计的是“跨过主边缝隙”的附加边不是“图上所有附加边”。4.2 可复现的 C 代码给一个能直接改改就交的版本。我用 vector 存图1 号点为根LOG 取 20n 在 2e5 级别足够如果 n 更大可以动态取LOG __lg(n) 2#include bits/stdc.h using namespace std; const int N 200005; const int LOG 20; int n, m; vectorint g[N]; int depth[N], up[LOG][N]; int diff[N], cnt[N]; long long ans 0; void dfs_pre(int u, int fa) { up[0][u] fa; for (int k 1; k LOG; k) { up[k][u] up[k - 1][up[k - 1][u]]; } for (int v : g[u]) { if (v fa) continue; depth[v] depth[u] 1; dfs_pre(v, u); } } int lca(int a, int b) { if (depth[a] depth[b]) swap(a, b); int d depth[a] - depth[b]; for (int k LOG - 1; k 0; k--) { if (d (1 k)) a up[k][a]; } if (a b) return a; for (int k LOG - 1; k 0; k--) { if (up[k][a] ! up[k][b]) { a up[k][a]; b up[k][b]; } } return up[0][a]; } void dfs_calc(int u, int fa) { cnt[u] diff[u]; for (int v : g[u]) { if (v fa) continue; dfs_calc(v, u); cnt[u] cnt[v]; } if (fa ! 0) { if (cnt[u] 0) ans m; else if (cnt[u] 1) ans 1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs_pre(1, 0); for (int i 0; i m; i) { int u, v; cin u v; int l lca(u, v); diff[u]; diff[v]; diff[l] - 2; } dfs_calc(1, 0); cout ans \n; return 0; }需要注意这段代码假设输入顺序是先 n-1 条主边、后 m 条附加边。实际提交时看题面给的是哪种我自己写题解的时候经常栽在这里。如果题目要求输出具体方案那还需要在打标记时存下附加边的端点但本题只需要计数不需要输出“选哪条附加边”所以在线处理完全没问题。4.3 两个极易踩的坑根节点的幽灵边与栈递归深度第一个坑是根节点统计。dfs_calc 里我用了if (fa ! 0)来判断当前节点是否有对应的父边。如果你写成if (u ! 1)一旦根不止一个或者你换根就会漏计或误计。根节点的 cnt[1] 表示“1 号点到它的父亲之间那条不存在的边”被覆盖多少次这个值没有意义不能加入答案。第二个坑是类型。n 和 m 到 1e5 量级时最坏答案接近 (n-1) * m大约是 1e10int 直接溢出答案必须用 long long。很多人的代码逻辑完全正确却因为 ans 是 int 而 WA这种问题在 OJ 上很容易被阴。另外别忘了 main 开头那两行 ios 加速不然输入量大时容易在 IO 上多吃几倍时间。5. 从这道题看边差分模型的迁移套路5.1 点差分和边差分的记忆方法学完这题最容易混淆的是“点差分”和“边差分”的标记到底差在哪。我提供一个自己的记忆方式路径 u-v核心是 lca 处怎么扣。点差分路径上的“点”都 1lca 这个点本身也要算进来所以diff[u], diff[v], diff[lca]--, diff[fa[lca]]--。边差分路径上的“边”都 1相当于给每条边的“子节点”1而 lca 对应的边不参与路径所以diff[u], diff[v], diff[lca]-2。为什么边差分不用管 fa[lca]因为边差分在统计时根本没有“父边”的概念减 2 在 lca 处正好把 u、v 两路上传的公共部分全部抵消。点差分里 lca 节点本身有贡献需要一个 -1它的父边不参与路径再用一个 -1 传递到父节点。两个模型虽然只差一个位置背后的几何意义完全不同。建议每次做题前先写一句话问自己统计的是节点权值还是边权值是在树上路径还是树链区间答案自然就出来了。5.2 一类题的共同骨架路径加 统计覆盖 分类计数闇の連鎖看起来套路化但其实代表了一大类“树上路径覆盖计数”题目。核心流程永远是dfs 预处理出 depth 和倍增表或树剖 dfn。对每条路径 (u, v)用差分打标记。再一次 dfs 后序累加得到每条边或每个点的覆盖次数。按题目要求分类计数或求最值。比如换一个问法给定若干条路径问每条边被多少条路径覆盖那就是去掉第 4 步直接输出 cnt。再比如问“删掉哪条边能最大程度破坏连通性”就变成统计覆盖次数后找最小值或最大值。这套骨架我刷了不少题都是同一个味道区别主要在差分标记的位置和统计阶段的语义所以把原理吃透比背代码重要得多。5.3 做题顺序建议与自测用例最后给一个自测用例保证你代码逻辑没问题。树为 1-2, 2-3, 2-4三条附加边是 3-1, 3-4以及再来一条 3-4重边。手动推附加边 3-1 覆盖 1-2 和 2-3第一条 3-4 覆盖 2-3 和 2-4第二条重边同样覆盖 2-3 和 2-4。于是边 1-2 的覆盖次数为 1边 2-3 为 3边 2-4 为 2。答案只有 cnt1 的一条主边贡献 1其余贡献 0总方案 1。拿这组数据跑一遍再对比手推的 diff 数组能快速定位是 LCA 错了还是差分扣错了。我个人的做题习惯是每次拿到这种树上差分题先在草稿纸上画一棵 5 个点以内的小树把所有端点和 lca 的标记手写出来再开始敲代码。这样写出来的代码基本能一次过样例而不是靠反复试错去蒙。闇の連鎖这道题的模型太经典吃透之后你会发现自己再看其他路径覆盖类题目脑子里会直接浮现出diff[u], diff[v], diff[lca]-2这一行剩下的都只是套壳。