看到“闇の連鎖”这个标题，我第一反应是哪个番的剧情，直到打开题面才发现：这是经典的树上差分模型题，考察的就是边差分 + 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] = 0：e 本身就是桥。删掉它树已经分裂，第二把刀附加边随便选哪条都行，方案贡献 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] += 1，d[r+1] -= 1，最后做前缀和还原。树上差分本质是同一思想搬到树结构上，只是“前缀和”变成了“从叶子到根的累加”。
在树上，任何一条简单路径 u -> v 都可以看成两部分：u 往上到 lca，v 往上到 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]=1，cnt[2]=cnt[3]+d[2]=1，cnt[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 == v，LCA 就是它自己。这些情况在差分标记里都不会出问题，因为 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 cnt=0、cnt=1、cnt>=2 分别对应几次有效切割
其实在 1.3 已经推导过结论，这里再从实现角度重述一遍：对每一条主边，也就是对根节点之外的所有节点 u，检查 cnt[u] 的值。
| 条件 | 含义 | 附加边选择 | 方案贡献 |
|---|---|---|---|
| cnt[u] == 0 | 该主边是桥 | m 条附加边任选其一 | +m |
| cnt[u] == 1 | 唯一一条附加边跨过它 | 必须选那条附加边 | +1 |
| cnt[u] >= 2 | 至少两条附加边跨过它 | 选任一条都不够断开 | +0 |
为什么 cnt=0 时附加边可以任意选？因为删掉主边后树已经分裂，再删的附加边无论连接的是左块内部还是右块内部，都不会再把两块接回去。这里不要带普通图的直觉——附加边再多，它们也不参与主干连接，只要主桥断开，整图必裂。cnt 统计的是“跨过主边缝隙”的附加边，不是“图上所有附加边”。
4.2 可复现的 C++ 代码
给一个能直接改改就交的版本。我用 vector 存图，1 号点为根，LOG 取 20（n 在 2e5 级别足够；如果 n 更大，可以动态取LOG = __lg(n) + 2）：
#include <bits/stdc++.h> using namespace std; const int N = 200005; const int LOG = 20; int n, m; vector<int> 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，大约是 1e10，int 直接溢出，答案必须用 long long。很多人的代码逻辑完全正确，却因为 ans 是 int 而 WA，这种问题在 OJ 上很容易被阴。另外别忘了 main 开头那两行 ios 加速，不然输入量大时容易在 IO 上多吃几倍时间。
5. 从这道题看边差分模型的迁移套路
5.1 点差分和边差分的记忆方法
学完这题最容易混淆的，是“点差分”和“边差分”的标记到底差在哪。我提供一个自己的记忆方式：路径 u->v，核心是 lca 处怎么扣。
- 点差分：路径上的“点”都 +1，lca 这个点本身也要算进来，所以
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。答案只有 cnt=1 的一条主边贡献 1，其余贡献 0，总方案 1。拿这组数据跑一遍，再对比手推的 diff 数组，能快速定位是 LCA 错了还是差分扣错了。
我个人的做题习惯是，每次拿到这种树上差分题，先在草稿纸上画一棵 5 个点以内的小树，把所有端点和 lca 的标记手写出来，再开始敲代码。这样写出来的代码基本能一次过样例，而不是靠反复试错去蒙。闇の連鎖这道题的模型太经典，吃透之后，你会发现自己再看其他路径覆盖类题目，脑子里会直接浮现出diff[u]++, diff[v]++, diff[lca]-=2这一行，剩下的都只是套壳。
