第一次在USACO历年题里刷到Max Flow P的时候我还没系统接触过树上差分。当时看到给一棵树K条路径每条路径经过的所有点点权1最后问最大点权——第一反应就是暴力每条路径从u往v跑一遍DFS沿途把所有点加1。结果代码写出来一测数据直接给我上了一课。N是5×10^4K是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在 r1 处开始少 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 这个点被路径覆盖的次数。很多人第一次看到这个公式会懵怎么一个端点加1LCA要减1LCA的父节点还要减1为什么不是cnt[p] - 2我用贡献视角来解释一次。做子树和的本质是每个节点上的标记会向上影响它的所有祖先。所以一次操作中u 上的 1会使 u 的所有祖先节点最终值都 1v 上的 1会使 v 的所有祖先节点最终值都 1p 上的 -1会使 p 以及 p 以上所有祖先都 -1fa[p] 上的 -1会使 fa[p] 以及 fa[p] 以上所有祖先都 -1。现在把这些贡献叠加起来看在 p 这个点u 的 1 能影响到这儿v 的 1 能影响到这儿p 自己的 -1 也在它自己身上生效fa[p] 的 -1 则不会传到 p。所以 p 最终净变化是 11-11。这正好表示 p 本身在路径上被覆盖一次。在 fa[p] 这个点u 的 1 能传到这儿v 的 1 能传到这儿p 的 -1 也能传到这儿fa[p] 的 -1 在自己的位置生效。所以 fa[p] 净变化是 11-1-10。fa[p] 确实不在路径上不该被覆盖。在 fa[p] 以上的任意祖先 x四个标记全都能影响 x11-1-10也不会被误覆盖。这就是为什么点差分需要 cnt[p]-- 还要再补一个 cnt[fa[p]]--一次 -1 只能让 p 本身的重复计数被消掉一次但两个端点的 1 在 fa[p] 处还会多出一个 1需要用第二个 -1 在更上一层把它拦下来。3.2 两个经典例子手工推演只看公式还是抽象我建议你自己动手推两个极端例子推完这个知识点基本就长在脑子里了。第一个例子是链状树节点 1-2-3-4 排成一条链根为 1。一次操作路径 (2, 4)。此时 LCA(2,4) 2fa[2] 1。打标记cnt[2] → 1cnt[4] → 1cnt[2]-- → 0cnt[1]-- → -1从叶子向根做子树和也就是把当前节点的标记累加到父节点节点4cnt[4]1累加到3cnt[3]1节点3cnt[3]1累加到2cnt[2]011节点2cnt[2]1累加到1cnt[1]-110。最终 cnt[2]1, cnt[3]1, cnt[4]1cnt[1]0。完全正确路径 2→4 经过 2、3、4不经过 1。第二个例子是分叉树根1节点2是1的孩子3和4都是2的孩子。一次操作路径 (3, 4)。LCA(3,4)2fa[2]1。打标记cnt[3] → 1cnt[4] → 1cnt[2]-- → -1cnt[1]-- → -1子树和恢复节点3cnt[3]1累加到2cnt[2]-110节点4cnt[4]1累加到2cnt[2]011节点2cnt[2]1累加到1cnt[1]-110。最终 cnt[2]1, cnt[3]1, cnt[4]1cnt[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[u], cnt[v], cnt[p]--, cnt[fa[p]]--cnt[x] 表示点 x 被路径覆盖次数边权cnt[u], cnt[v], cnt[p] - 2cnt[x] 表示点 x 与父节点之间的边被覆盖次数做题之前先想清楚这题问的是点还是边别把两个公式记串了。我见过好几个同学把点差分写成 cnt[p] - 2结果 lca 的位置少算1对比样例死活对不上。4. 标记恢复不是只能再写一次DFS深度倒推法的原理与实现4.1 “把标记推向父节点”和DFS恢复是同一件事打完所有操作的标记之后我们面对的是一个散落在各个节点上的 cnt 数组。现在需要做一次子树和把标记汇聚成每个点的真实覆盖次数。最标准的方法自然是再写一个 DFS后序遍历每个点先递归子树再把自己的 cnt 加上所有子节点的返回值。这个方法好理解但有两个小麻烦一是要多写一个递归函数二是第二次递归会和第一次建 LCA 表的 DFS 产生一定代码重复。其实可以换个视角理解子树和。后序遍历做子树和的时候本质上就是每个节点把汇总好的值向上传给父节点。既然这样我完全可以不递归直接按深度从大到小遍历所有节点每遇到一个节点 u就把 cnt[u] 累加到 cnt[fa[u]] 上。4.2 按深度倒推的完整逻辑为什么从深度大到小就是对的因为一个节点的子树和只需要它所有后代节点的标记都汇聚到它自己身上。深度最大的节点一定是叶子没有后代它的 cnt 就是自己的标记把它加到父节点上等于把叶子贡献传了上去。等到处理父节点时所有子节点的贡献都已经到位了这时父节点再把汇总后的值继续上传。这个过程在深度递减的顺序下天然保证先处理子孙再处理祖先。具体代码是这样vectorint 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((nk) log n)在这个数据范围下没有任何压力。4.3 根节点和0号节点的一个隐藏边界深度倒推时一定要跳过根节点因为根节点的父节点是0。如果你不跳过执行cnt[0] cnt[root]就等于把根上的覆盖次数传到了一个不存在的节点上虽然一般不会影响最终答案因为统计最大值时只遍历1到n但数组越界或者无意义的修改很容易在调试时干扰视线。更需要注意的是打标记阶段。如果 lca 刚好就是根节点1那么cnt[fa[p]]--实际上操作的是cnt[0]--。这在全局数组下是可以运行的因为数组下标0合法但如果在某些用 vector 且只 resize 到 n1 的写法里就可能越界。我的习惯是打标记时判断一下if (up[p][0] ! 0) cnt[up[p][0]]--;这样既不会碰0号节点语义也更明确fa[p] 存在才需要减。5. 完整可AC代码与复杂度核算含LCA实现细节5.1 完整C17代码下面给出我这道题的完整实现。树的存储用邻接表LCA用倍增法差分恢复用深度倒推整份代码可以直接交到洛谷。#include bits/stdc.h using namespace std; const int N 50005; const int LOG 20; vectorint 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]]--; } vectorint 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 是为了省心。n5×10^42^1665536 已经够了但取 20 也可以预处理时多循环几次时间上没有区别。数组开 50005 是题目数据范围你实际写的时候开 50005 或 50010 都行留一点余量总没错。5.2 复杂度核算与常数优化整体复杂度分为三部分阶段复杂度说明DFS 预处理倍增表O(n log n)每个节点处理 log n 个祖先k 次操作查 LCA 打标记O(k log n)每次 LCA 查询 O(log n)打标记 O(1)子树和恢复O(n log n)主要是排序实际累加是 O(n)总复杂度 O((nk) log n)。代入 n5×10^4、k10^5数学运算量大约在几百万的量级一秒之内轻松跑完。常数优化方面如果你不排序也可以在 DFS 的时候用一个 vector 按节点访问顺序存下来再把深度作为 key 做一次稳定排序。只不过这道题没必要扣这么细一次 sort 才 5 万个数耗时完全可以忽略。另外读入方面ios::sync_with_stdio(false); cin.tie(nullptr);已经够稳。如果遇到特别老的 OJ 对输入输出要求严格可以换 scanf/printf 读入但洛谷上这份代码直接过。6. 实战中那些容易翻车的细节栈、边界、长整型与自测6.1 递归深度与栈空间第一次 DFS 建倍增表用的是递归实现。n5×10^4最坏情况树是一条链递归深度就是 5×10^4。在洛谷的评测环境下默认栈空间一般没问题但某些 OJ 或者本地 Windows 环境栈空间比较小递归过深容易爆栈。如果遇到爆栈有两条路一是把 DFS 改成手写栈迭代实现虽然代码会长不少二是给递归加编译选项比如在本地用-Wl,--stack67108864这类方式扩大栈。竞赛时更稳妥的做法是条链数据少、或者直接用迭代 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 的深度。n5×10^4深度差最大不超过 5×10^42^1665536 足够覆盖所以 LOG 等于 17 也可以。开 20 更像是一种习惯多几个格子用不上也不浪费。读入优化如果不用ios::sync_with_stdio(false)cin 读 10^5 数量级的操作在部分 OJ 上可能有点悬。我这道题在本地测过关掉同步后 cin 和 scanf 差距已经很小不需要写快读。6.3 什么时候用 long long什么时候可以 int本题 cnt 数组用 int 足够。单点最多被覆盖 k 次k10^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 ≤ 10k ≤ 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(nk)之后打差分标记、恢复子树和的流程完全不变。洛谷 P3128 的数据范围不需要走这条路但如果以后遇到 n 和 k 都到 10^6 的变体题记得还有这个升级方案就行。树上差分本身的价值恰恰在于它把路径修改和离线 LCA两件事解耦了无论 LCA 怎么求差分的标记和恢复逻辑都不变。我实际教这题的时候一定会让学生先写暴力再用链状样例去手工推一遍差分标记最后才看代码。跳过这个推演过程直接背公式的人十有八九会把点差分和边差分搞混或者不知道为什么 lca 处要减两个1。这题的难点不在代码而在理解标记为什么长这样。理解了后面遇到任何树上路径统计题你都能很快判断出该用哪种差分、标记打在哪里。