树上差分与LCA：USACO Max Flow P 路径加一问题全解

第一次在USACO历年题里刷到Max Flow P的时候，我还没系统接触过树上差分。当时看到"给一棵树，K条路径，每条路径经过的所有点点权+1，最后问最大点权"——第一反应就是暴力：每条路径从u往v跑一遍DFS，沿途把所有点加1。结果代码写出来一测数据，直接给我上了一课。N是5×10^4，K是1×10^5，暴力复杂度O(NK)=5×10^9次操作，评测机再快也扛不住。后来才知道，这种"多次路径修改+最后统一查询"的问题，USACO里基本就是给你树上差分这个套路送分的。

这篇文章就把 P3128 从暴力到正解的完整思路、点差分的标记原理、恢复方式、以及我实际写题过程中踩过的坑全部整理出来。树剖能做这题，但为了这个数据范围特意写树剖属于杀鸡用牛刀；倍增LCA+树上差分是这里最舒服的解法，代码短、常数小、思路也直观。

1. 为什么“路径加一”必须换思路：先从暴力的复杂度算起

1.1 这题到底在问什么

先简单复述一下题目。给定一棵包含 n 个节点的树，编号 1 到 n。接下来有 k 次操作，每次给出一个起点 s 和一个终点 t，要求把 s 到 t 这条简单路径上的每一个节点的点权都加 1。所有操作结束之后，输出整棵树上点权的最大值。

注意这里统计的是点权，也就是每个节点本身要被算一次。后面你会看到，这一点直接决定了差分标记该往哪里打、该减几次。

我第一次看到数据范围的时候，心里想的还是"K次操作每次都从s走到t，每条边最多走一次，算上回溯也就2倍路径长度，能用多慢？"——问题就出在路径长度上。树的直径在最坏情况下就是n，也就是说一次操作最多能O(n)完成，k次操作就是O(nk)≈5×10^9。这个数字在竞赛环境里是完全跑不完的。

1.2 暴力到底慢在哪里

暴力做法的逻辑很简单：对每个操作，从 s 出发DFS到 t，沿途所有节点点权加1。代码也就十几行，甚至用不上LCA，直接递归找t就行。

但它的致命点是：每次操作都要重新走一遍整条路径。如果k组操作里有大量重叠路径，这些重叠部分本质上是在反复算同一个节点的加法。也就是说，暴力没有把"路径上的加1操作"做任何信息合并，每个节点的最终值只能等所有操作跑完才知道，那你中间每跑一次操作，前面所有操作的信息其实都已经体现在节点上了——可你最终还是得再扫一遍。

打个比方，这就好比你在一个本子上记100个人各自分别翻了哪个柜子，最后想知道哪个柜子被翻得最多次。如果每次都从头数一遍每个柜子被翻了几次，数据量大一点就非常吃力。

所以这类题的核心思路不是"加速单次路径遍历"，而是"把重复的路径覆盖信息压缩成少量点上的标记，最后统一做一次汇总"。

2. 一维差分的套路迁移到树上，先要回答三个问题

2.1 一维差分的核心：把区间加减换成四个点的记号

如果你熟悉一维线性差分，会知道这样一个代码片段：要对数组 a 的区间 [l, r] 内所有元素加 c，不需要真的循环从 l 加到 r，而是在差分数组上做两次更新：

diff[l] += c; diff[r + 1] -= c;

最后做一遍前缀和，a[i] = a[i-1] + diff[i]，就能还原出每个位置的最终值。

这个技巧之所以成立，是因为一维数组天然有一个"顺序结构"：前缀和从左到右依次累加，区间 [l,r] 加 c 变成在 l 处开始多 c，在 r+1 处开始少 c。

那问题来了：树上没有"从左到右"这种顺序，怎么把一个区间加的操作对应到树上？

2.2 树上的“前缀和”其实是子树和

树如果要模拟"前缀和"，最自然的对象是子树和：每个节点的最终值等于它的点权标记加上所有子树内点权标记之和。这个操作可以通过一次后序遍历完成，叶子先向上汇聚，根最后汇总。

这个"子树和"和一维前缀和一个重要的相似点在于：它们都是把多个单点标记进行累加，最后一次性恢复成真实值。一维前缀和是线性的顺序累加；树的子树和是自底向上的层层累加。

那么，如果我们要对路径 s→t 上所有节点加1，能不能把这条路径的覆盖信息打成几个"标记"，让最后做一遍子树和的时候，路径上的点恰好被累加1，路径外的点恰好不被累加？这就是树上差分要解决的核心问题。

2.3 为什么必须算LCA而不是用DFS序

到这里很多人会想：既然子树和可以处理树上的累加，那我能不能用DFS序把树压成一维数组，把路径对应成几个区间？

听上去可行，但实际操作不行。一条路径 s→t 在树的DFS序上并不是一个连续区间。它本质上是"s到lca的上半段"和"lca到t的下半段"拼接在一起，中间很可能横跨多个子树的DFS区间。就算你能把路径拆成两个区间，也必须保证lca处的点权没有被重复计算，还要处理lca的父节点边界——这复杂度和你直接写个LCA没区别了。

所以树上差分的做法里，LCA不是可选优化，而是必要环节。标记要打在路径的两个端点和它们的最近公共祖先附近，只有确定了LCA，才能让差分标记的"抵消"精准落在该落的位置。

3. 点差分标记公式：cnt[u]++, cnt[v]++, cnt[lca]--, cnt[fa[lca]]-- 的逐项推导

3.1 四个标记各司其职：谁加谁减、为什么

点差分的标准标记方式，对一次操作 (u, v)，设 p = lca(u, v)，fa[p] 为 p 的父节点：

cnt[u]++; cnt[v]++; cnt[p]--; cnt[fa[p]]--;

最后做一遍子树和，cnt[x] 就是 x 这个点被路径覆盖的次数。

很多人第一次看到这个公式会懵：怎么一个端点加1，LCA要减1，LCA的父节点还要减1？为什么不是cnt[p] -= 2？

我用"贡献视角"来解释一次。做子树和的本质是：每个节点上的标记，会向上影响它的所有祖先。所以一次操作中：

• u 上的 +1，会使 u 的所有祖先节点最终值都 +1；
• v 上的 +1，会使 v 的所有祖先节点最终值都 +1；
• p 上的 -1，会使 p 以及 p 以上所有祖先都 -1；
• fa[p] 上的 -1，会使 fa[p] 以及 fa[p] 以上所有祖先都 -1。

现在把这些贡献叠加起来看：

• 在 p 这个点：u 的 +1 能影响到这儿，v 的 +1 能影响到这儿，p 自己的 -1 也在它自己身上生效，fa[p] 的 -1 则不会传到 p。所以 p 最终净变化是 1+1-1=1。这正好表示 p 本身在路径上，被覆盖一次。
• 在 fa[p] 这个点：u 的 +1 能传到这儿，v 的 +1 能传到这儿，p 的 -1 也能传到这儿，fa[p] 的 -1 在自己的位置生效。所以 fa[p] 净变化是 1+1-1-1=0。fa[p] 确实不在路径上，不该被覆盖。
• 在 fa[p] 以上的任意祖先 x：四个标记全都能影响 x，1+1-1-1=0，也不会被误覆盖。

这就是为什么点差分需要 cnt[p]-- 还要再补一个 cnt[fa[p]]--：一次 -1 只能让 p 本身的重复计数被消掉一次，但两个端点的 +1 在 fa[p] 处还会多出一个 1，需要用第二个 -1 在更上一层把它拦下来。

3.2 两个经典例子手工推演

只看公式还是抽象，我建议你自己动手推两个极端例子，推完这个知识点基本就长在脑子里了。

第一个例子是链状树：节点 1-2-3-4 排成一条链，根为 1。一次操作路径 (2, 4)。此时 LCA(2,4) = 2，fa[2] = 1。打标记：

• cnt[2]++ → 1
• cnt[4]++ → 1
• cnt[2]-- → 0
• cnt[1]-- → -1

从叶子向根做子树和，也就是把当前节点的标记累加到父节点：

• 节点4：cnt[4]=1，累加到3，cnt[3]=1；
• 节点3：cnt[3]=1，累加到2，cnt[2]=0+1=1；
• 节点2：cnt[2]=1，累加到1，cnt[1]=-1+1=0。

最终 cnt[2]=1, cnt[3]=1, cnt[4]=1，cnt[1]=0。完全正确：路径 2→4 经过 2、3、4，不经过 1。

第二个例子是分叉树：根1，节点2是1的孩子，3和4都是2的孩子。一次操作路径 (3, 4)。LCA(3,4)=2，fa[2]=1。打标记：

• cnt[3]++ → 1
• cnt[4]++ → 1
• cnt[2]-- → -1
• cnt[1]-- → -1

子树和恢复：

• 节点3：cnt[3]=1，累加到2，cnt[2]=-1+1=0；
• 节点4：cnt[4]=1，累加到2，cnt[2]=0+1=1；
• 节点2：cnt[2]=1，累加到1，cnt[1]=-1+1=0。

最终 cnt[2]=1, cnt[3]=1, cnt[4]=1，cnt[1]=0。路径 3→4 经过3、2、4，也不经过1，正确。

这两个例子一个验证"LCA在端点处"的情况，一个验证"LCA在路径中间"的情况，恰好覆盖了点差分的两类关键边界。

3.3 点差分和边差分的区别：为什么这里是-1不是-2

树上有两种常见的差分目标：点权和边权。如果统计的是边权，标记规则是：

cnt[u]++; cnt[v]++; cnt[p] -= 2;

做子树和后，cnt[x] 表示 x 与父节点之间的那条边被覆盖了多少次。为什么这里要 -= 2？

因为边差分中，u 的 +1 和 v 的 +1 沿路径向上传导时，会在 p 处汇合，p 上方的那条边（p 到 fa[p]）并不在路径上，应该被清零。于是 p 处直接减2，把两个端点贡献上来的2抵消成0。p 自己这个点反而不重要了，因为统计对象是边。

点差分统计对象是点本身，p 必须保留1次覆盖，所以不能在 p 处减2，只能减1，剩下多的1放到 fa[p] 处去抵消。

给个表格对比，方便以后选标记方式不再犹豫：

做题之前先想清楚这题问的是点还是边，别把两个公式记串了。我见过好几个同学把点差分写成 cnt[p] -= 2，结果 lca 的位置少算1，对比样例死活对不上。

4. 标记恢复不是只能再写一次DFS：深度倒推法的原理与实现

4.1 “把标记推向父节点”和DFS恢复是同一件事

打完所有操作的标记之后，我们面对的是一个散落在各个节点上的 cnt 数组。现在需要做一次"子树和"，把标记汇聚成每个点的真实覆盖次数。

最标准的方法自然是再写一个 DFS，后序遍历，每个点先递归子树，再把自己的 cnt 加上所有子节点的返回值。这个方法好理解，但有两个小麻烦：一是要多写一个递归函数，二是第二次递归会和第一次建 LCA 表的 DFS 产生一定代码重复。

其实可以换个视角理解子树和。后序遍历做子树和的时候，本质上就是每个节点把汇总好的值"向上传给父节点"。既然这样，我完全可以不递归，直接按深度从大到小遍历所有节点，每遇到一个节点 u，就把 cnt[u] 累加到 cnt[fa[u]] 上。

4.2 按深度倒推的完整逻辑

为什么从深度大到小就是对的？因为一个节点的子树和，只需要它所有后代节点的标记都汇聚到它自己身上。深度最大的节点一定是叶子，没有后代，它的 cnt 就是自己的标记；把它加到父节点上，等于把叶子贡献传了上去。等到处理父节点时，所有子节点的贡献都已经到位了，这时父节点再把汇总后的值继续上传。这个过程在深度递减的顺序下天然保证"先处理子孙，再处理祖先"。

具体代码是这样：

vector<int> order(n + 1); iota(order.begin() + 1, order.end(), 1); sort(order.begin() + 1, order.end(), [&](int a, int b) { return depth[a] > depth[b]; }); for (int u : order) { if (u == root) continue; cnt[up[u][0]] += cnt[u]; }

注意这里我用up[u][0]表示 u 的父节点，就是倍增表的第一维。因为我已经在预处理 LCA 时把所有节点的父节点记录下来了，恢复标记的时候直接查表就行，不需要再对树做一次递归。

这种写法的好处是：代码不容易在第二次 DFS 时把递归的入口或边界写错，而且整体思路非常线性，配合sort即使把排序算进去，总复杂度依然是 O((n+k) log n)，在这个数据范围下没有任何压力。

4.3 根节点和0号节点的一个隐藏边界

深度倒推时一定要跳过根节点，因为根节点的父节点是0。如果你不跳过，执行cnt[0] += cnt[root]，就等于把根上的覆盖次数传到了一个不存在的节点上，虽然一般不会影响最终答案（因为统计最大值时只遍历1到n），但数组越界或者无意义的修改很容易在调试时干扰视线。

更需要注意的是打标记阶段。如果 lca 刚好就是根节点1，那么cnt[fa[p]]--实际上操作的是cnt[0]--。这在全局数组下是可以运行的，因为数组下标0合法，但如果在某些用 vector 且只 resize 到 n+1 的写法里就可能越界。

我的习惯是打标记时判断一下：

if (up[p][0] != 0) cnt[up[p][0]]--;

这样既不会碰0号节点，语义也更明确：fa[p] 存在才需要减。

5. 完整可AC代码与复杂度核算（含LCA实现细节）

5.1 完整C++17代码

下面给出我这道题的完整实现。树的存储用邻接表，LCA用倍增法，差分恢复用深度倒推，整份代码可以直接交到洛谷。

#include <bits/stdc++.h> using namespace std; const int N = 50005; const int LOG = 20; vector<int> g[N]; int depth[N], up[N][LOG]; int cnt[N]; void dfs(int u, int fa) { depth[u] = depth[fa] + 1; up[u][0] = fa; for (int i = 1; i < LOG; i++) { up[u][i] = up[up[u][i - 1]][i - 1]; } for (int v : g[u]) { if (v == fa) continue; dfs(v, u); } } int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; for (int i = 0; i < LOG; i++) { if (diff >> i & 1) u = up[u][i]; } if (u == v) return u; for (int i = LOG - 1; i >= 0; i--) { if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return up[u][0]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); while (k--) { int u, v; cin >> u >> v; int p = lca(u, v); cnt[u]++; cnt[v]++; cnt[p]--; if (up[p][0] != 0) cnt[up[p][0]]--; } vector<int> order(n + 1); iota(order.begin() + 1, order.end(), 1); sort(order.begin() + 1, order.end(), [&](int a, int b) { return depth[a] > depth[b]; }); for (int u : order) { if (u == 1) continue; cnt[up[u][0]] += cnt[u]; } int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, cnt[i]); } cout << ans << '\n'; return 0; }

代码里LOG取 20 是为了省心。n=5×10^4，2^16=65536 已经够了，但取 20 也可以，预处理时多循环几次，时间上没有区别。数组开 50005 是题目数据范围，你实际写的时候开 50005 或 50010 都行，留一点余量总没错。

5.2 复杂度核算与常数优化

整体复杂度分为三部分：

总复杂度 O((n+k) log n)。代入 n=5×10^4、k=10^5，数学运算量大约在几百万的量级，一秒之内轻松跑完。

常数优化方面，如果你不排序，也可以在 DFS 的时候用一个 vector 按节点访问顺序存下来，再把深度作为 key 做一次稳定排序。只不过这道题没必要扣这么细，一次 sort 才 5 万个数，耗时完全可以忽略。

另外读入方面，ios::sync_with_stdio(false); cin.tie(nullptr);已经够稳。如果遇到特别老的 OJ 对输入输出要求严格，可以换 scanf/printf 读入，但洛谷上这份代码直接过。

6. 实战中那些容易翻车的细节：栈、边界、长整型与自测

6.1 递归深度与栈空间

第一次 DFS 建倍增表用的是递归实现。n=5×10^4，最坏情况树是一条链，递归深度就是 5×10^4。在洛谷的评测环境下默认栈空间一般没问题，但某些 OJ 或者本地 Windows 环境栈空间比较小，递归过深容易爆栈。

如果遇到爆栈，有两条路：一是把 DFS 改成手写栈迭代实现，虽然代码会长不少；二是给递归加编译选项，比如在本地用-Wl,--stack=67108864这类方式扩大栈。竞赛时更稳妥的做法是条链数据少、或者直接用迭代 DFS 建表。我个人建议：平时练习时就养成"看到 n 到 10^5 级别递归就警惕"的意识，而不是等爆了再临时改。

6.2 LCA的边界、数组大小与读入优化

写 LCA 时最容易错的是这个循环：

for (int i = LOG - 1; i >= 0; i--) { if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } }

很多新手会把条件写成while (up[u][i] != up[v][i])，在一层里反复跳，这是错的。倍增跳 LCA 的精髓是从大到小枚举二进制位，每个位最多跳一次，像凑数字一样把两个节点跳到 LCA 的下一层。

数组大小方面，up[N][LOG]一定不要开成up[N][20]却把循环写成i < LOG时没问题，但如果你把 LOG 定义成 17 就要保证 2^17 确实超过 n 的深度。n=5×10^4，深度差最大不超过 5×10^4，2^16=65536 足够覆盖，所以 LOG 等于 17 也可以。开 20 更像是一种习惯，多几个格子用不上也不浪费。

读入优化：如果不用ios::sync_with_stdio(false)，cin 读 10^5 数量级的操作在部分 OJ 上可能有点悬。我这道题在本地测过，关掉同步后 cin 和 scanf 差距已经很小，不需要写快读。

6.3 什么时候用 long long，什么时候可以 int

本题 cnt 数组用 int 足够。单点最多被覆盖 k 次，k=10^5，远小于 int 上限约 2.1×10^9。

但如果你以后做别的树上差分题，看到 k 的范围超过 10^9，或者操作不只是 +1 而是加一个较大的权值，一定要把 cnt 和答案都改成 long long。这种"看着像 int、实际可能爆"的题我踩过不止一次，每次都是对拍半天发现大数据答案不对，最后发现是类型宽度不够。

6.4 构造自测样例的三个方法

写完代码不能直接交，我一般会构造几类数据自测：

第一，链状树。1-2-3-4-5 这种形状，能测出深度较深时 LCA 跳转是否正确。

第二，星形树。节点1连着2、3、4、5，这种树 LCA 常常就是根，专门用来验证 lca 为根节点时cnt[fa[p]]--的边界处理。

第三，随机小树 + 随机操作，拿暴力代码对拍。暴力代码不写差分，每次操作直接在父节点数组上从 u 向上走到 LCA、再从 v 向上走到 LCA，把路径上节点计数加1。数据范围控制在 n ≤ 10，k ≤ 10，随机跑几百组，两组答案完全一致才说明差分公式用对了。

这个方法虽然土，但它是检验公式记忆最直接的方式。点差分和边差分如果搞混，或者 lca 处减多了，暴力对拍立刻能暴露问题。

7. 从Max Flow扩展出去：边差分和其他应用场景

7.1 如果题目把“点权”换成“边权”

USACO 里经常有变体：给路径上所有边加1，最后问哪条边被覆盖次数最多。这时就不能用点差分的公式了，要改成开头提到过的边差分。

边差分的打标记方式是cnt[u]++ , cnt[v]++ , cnt[lca] -= 2。做完子树和后，cnt[x] 代表 x 与父节点之间的边。为什么 lca 处减2，第三章已经详细对比过，这里不再重复。关键是做题前一定先看统计对象是点还是边，两者标记规则差一个fa[lca]的操作。

我记得有一道同样经典的题——运输计划，就用到了边差分配合二分答案的思想，属于树上差分的高级应用。如果你把 P3128 的点差分和边差分都吃透了，那道题的核心就不难理解了。

7.2 当k很大时：离线Tarjan + 差分的思路

倍增 LCA 的复杂度是每次查询 O(log n)。如果 k 达到 10^6 甚至更高，log n 的查询可能成为瓶颈。这时候可以改用 Tarjan 离线 LCA：一次 DFS 处理所有询问的 LCA，总复杂度 O(n+k)，之后打差分标记、恢复子树和的流程完全不变。

洛谷 P3128 的数据范围不需要走这条路，但如果以后遇到 n 和 k 都到 10^6 的变体题，记得还有这个升级方案就行。树上差分本身的价值，恰恰在于它把"路径修改"和"离线 LCA"两件事解耦了：无论 LCA 怎么求，差分的标记和恢复逻辑都不变。

我实际教这题的时候，一定会让学生先写暴力，再用链状样例去手工推一遍差分标记，最后才看代码。跳过这个推演过程，直接背公式的人十有八九会把点差分和边差分搞混，或者不知道为什么 lca 处要减两个1。这题的难点不在代码，而在理解标记为什么长这样。理解了，后面遇到任何树上路径统计题，你都能很快判断出该用哪种差分、标记打在哪里。