信奥赛C提高组CSP-S之树上差分先问一个问题当一道图论题要求在树上做多次路径修改最后询问每个点或每条边被覆盖的次数时你会想到什么如果第一反应是树链剖分或者LCT那说明你已经掌握了不少高级数据结构——但CSP-S考场上时间那么紧代码量越大越容易出错。其实这种问题的正解往往是一个原理极简、代码极短的技巧树上差分。我第一次接触树上差分是在准备CSP-S模拟赛的时候。当时有一道题给出一棵有N个点的树有M次操作每次把从u到v路径上的所有点权值加1最后输出所有点的最终权值。我上来就写了树剖洋洋洒洒两百行调试了很久。旁边某位选手用了不到五十行代码一个DFS就把问题解决得干干净净。那次之后我彻底记住了树上路径修改、离线统计覆盖次数优先考虑差分想都不用想。这篇文章我想把树上差分这套东西彻底讲透。它本质上就是把一维数组差分的思路推广到树上配合LCA最近公共祖先完成路径覆盖统计。适合已经掌握基础DFS、会写倍增LCA、正准备冲击CSP-S提高组一等奖的选手阅读当然如果你还在普及组荣升提高组的过渡期这篇文章也能帮你提前把这颗图论专题的钉子钉牢。1. 从一维差分说起树上差分的根基在哪里很多人学树上差分的时候卡住不是因为树上差分本身难而是因为没有把一维差分的为什么真正想明白。我们就从这里开始。所谓一维差分就是对数组a构造差分数组d使得d[1]a[1]d[i]a[i]-a[i-1]i≥2。这样对区间的修改操作就变成了对差分数组端点的修改比如要把区间[l, r]每个数加v只需要d[l]vd[r1]-v。全部修改完成后对差分数组做一次前缀和就能还原出每个位置的实际值。为什么要这么绕一圈因为单点修改是O(1)的区间修改如果暴力做是O(n)的而差分把区间修改压缩成了两次单点修改本质上是把区间信息编码到端点里。树上差分做的是同一件事把树上路径的修改压缩成少数几个点的标记修改最后通过一次DFS相当于树上的前缀和还原每个点或每条边的真实值。理解了这个思想树上差分的所有公式都不需要死记——它们全是想办法把一个路径修改表达成端点标记的自然结果。这里有一个非常关键的类比一维数组的前缀和是一个线性过程从d[1]一路加到d[i]树上的前缀和其实就是一个后序DFS每个节点的真实值等于它的差分值加上所有子节点的真实值之和。我第一次想明白这一点的时候感觉像是打通了任督二脉——树上差分和树上DP的根本思路其实是一致的子树信息向上汇聚。再看一维差分的正确性区间[l, r]加v为什么要在r1处减回来因为前缀和会把l处的加号一路带到最后如果不在右边界之后减掉加号就会溢出到r之后的所有位置。树上差分也是同样的道理路径修改只会影响路径上的点如果不做抵消影响就会扩散到不该受影响的地方。理解了这个扩散与抵消的博弈后面点差分和边差分的公式推起来就非常自然。2. 点差分与边差分两条公式一个思想树上差分具体怎么操作我们分两种情况给点加权还是给边加权。这两种情况的公式长得不一样很多初学者在这里记混但其实只要画出图来推一遍就永远忘不了。2.1 点差分路径覆盖计数先看最常见的点差分。给定一棵树M次操作每次把从u到v路径上的所有点权值加1注意包含u和v最终求每个点的权值。我们设差分数组为diff初始全0。每次操作用LCA把它拆成四个标记diff[u] 1 diff[v] 1 diff[lca] - 1 diff[parent(lca)] - 1然后从根开始做一次DFS后序每个点的最终值 diff[该点] 所有子节点的最终值之和。注意这里的最终值本身就是答案不需要再额外处理。为什么要这样拆我们倒数第二层来理解。假设路径u-v可以拆成两段u到lcalca到v。如果我们不用任何抵消机制只做diff[u]1和diff[v]1那么后序累加的时候从u和v向上走两股加号会在lca处汇合叠加一次再继续向上传播到根。这会导致两个问题第一lca会被多算一次因为两股加号都贡献到它头上第二加了应该只作用到lca为止但现在会一路传到根。所以我们需要在lca处减一次diff[lca]-1抵消掉多算的那次在parent(lca)处再减一次把不该继续上传的溢出拦住。这就是为什么点差分需要四个标记而不是两个。我再用大白话翻译一遍diff[u]1和diff[v]1相当于u和v分别向根方向发射了一股信号信号沿着父指针一路传播两股信号在lca处重叠导致lca被算两次就在lca减一次两股信号本应到此为止再向上就是超出路径的非法区域所以在lca的父亲处再减一次切断信号继续上传的路径。完美。2.2 边差分路径覆盖统计的另一种姿势再看边差分。有些题统计的不是点的覆盖次数而是边的覆盖次数比如给u到v的路径上每条边加1最后求每条边被覆盖多少次。边和点的区别在于树上的边可以用子节点来唯一标识——每条边对应一个子节点把树根之后每个非根节点都关联着它和父亲之间的那条边。所以边差分其实和点差分非常相似只需要在标记点数上做调整。边差分的每次操作标记是diff[u] 1 diff[v] 1 diff[lca] - 2看到区别了吗点差分减了两下边差分只减一下而且是减2。原因在于边差分统计的是子节点所代表的边路径上的点集包含lca但路径上的边集不包含lca与它的父节点之间那条边。两股信号在lca处汇合后lca本身被算了两次但lca对应的那条边即lca与父节点之间连着的边并不在路径上所以要在lca处一次性减掉2既抵消了lca被重复计算的两次又阻止了信号继续向上传。如果你把边差分和点差分并排对比会发现逻辑其实是一致的因为它们本质上都是对树上若干段路径修改做端点编码只是编码的单位不同——点差分的最小单位是点边差分的最小单位是边也就是非根节点与父亲的绑定关系。以下是两者的对比建议直接收藏差分类型操作对象每次修改的差分标记还原方式适用场景点差分点权diff[u], diff[v], diff[lca]--, diff[parent(lca)]--后序累加子节点值 自身diff路径上所有点覆盖次数、点权批量更新边差分边权等价于非根节点diff[u], diff[v], diff[lca]-2后序累加子节点值 自身diff路径上所有边覆盖次数、最小割计数、最短路覆盖记不住的时候不用硬背画棵树从u、v分别向根画箭头在lca处观察哪里重叠、哪里需要截断公式自然就出来了。2.3 一条链上的直觉验证理论说了这么多我们用最简单的一条链来验证公式比打一百行代码都管用。假设树是一条链1-2-3-4-5根是1。现在要统计从2到4路径上所有点的覆盖次数且每个点初始为0。按照点差分的公式lca(2,4)2parent(2)1所以标记为diff[2]1diff[4]1diff[2]-1diff[1]-1。合并后diff[4]1diff[2]0diff[1]-1其他为0。后序DFS累加5的最终值 diff[5]04的最终值 diff[4] 5的值 13 0 4的值 12 diff 2 3的值 11 diff 1 2的值 0。结果2、3、4各覆盖一次完全正确——路径恰好是2-3-4。再看边差分统计2到4的边覆盖。lca(2,4)2标记为diff[2]1diff[4]1diff[2]-2即diff[2]-1diff[4]1。后序累加41312(-1)1010。哪个节点值非零3和4。对应边分别是3-2和4-3正好是2到4路径上的两条边。完美。注意个细节边差分时节点3的值等于边3-2的覆盖次数节点4的值等于边4-3的覆盖次数。这个不对应经常让初学者困惑本质原因就是上面说的——边是用子节点做代表的。3. 核心套路拆解从LCA预处理到DFS汇总的完整模板公式会推了接下来就是把整条流程串成一个可以在考场上快速实现的固定模板。我把树上差分解题的完整链路拆成四步每一步都包含必须注意的实现细节。3.1 第一步建树确定根和深度建树没太多好说的用邻接表vector 存图。有一个值得关注的决策点是根的选择——根选哪里对于无根树任选一个节点作为根都是正确的树上差分不依赖根的位置因为路径是确定的LCA是确定的标记公式也不变。但实际做题时我会习惯性选1号点或者度数较大的节点作为根这样能减少递归深度降低爆栈的概率。这里要特别提醒树上差分的DFS汇总是在后序进行的递归深度最坏情况下等于树的高度。如果树是一条链递归深度会到10^5甚至更多有爆栈风险。竞赛中如果遇到毒瘤链数据建议用递归栈空间优化编译选项加-Wl,--stack268435456或者干脆改成手动模拟栈的迭代DFS。CSP-S的Linux环境栈通常给得比较宽松但如果你的DFS函数里开了太多局部变量还是要小心。3.2 第二步倍增LCA预处理树上差分的前提是能在O(log n)时间内求出任意两点的LCA。我推荐倍增法因为它的预处理代码和查询代码都很规整不容易写错。核心代码如下const int MAXN 100005; const int LOG 17; // 2^17 1e5 int n, m; vectorint g[MAXN]; int depth[MAXN]; int fa[MAXN][LOG]; void dfs_lca(int u, int father) { fa[u][0] father; depth[u] depth[father] 1; for (int i 1; i LOG; i) fa[u][i] fa[fa[u][i-1]][i-1]; for (int v : g[u]) { if (v father) continue; dfs_lca(v, u); } } int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); int delta depth[u] - depth[v]; for (int i 0; i LOG; i) if (delta (1 i)) u fa[u][i]; if (u v) return u; for (int i LOG - 1; i 0; --i) if (fa[u][i] ! fa[v][i]) { u fa[u][i]; v fa[v][i]; } return fa[u][0]; }有几个细节值得注意。第一LOG取多少一般取17或18对应1e5量级的n稳妥起见可以直接取20。遍历二进制位时从高到低跳这个顺序不能反。第二在向上对齐深度的循环里delta (1 i)判定后直接跳跳完别忘了更新u。第三后面那个循环的判断条件是fa[u][i] ! fa[v][i]不是depth别和前面的对齐循环混了——我第一次写的时候就在这里栽过跟头。如果你对倍增LCA的常数不满意树是n1e5、操作m1e5时倍增完全够用也可以换Tarjan离线LCA或者欧拉序RMQ。但说实话在树上差分的场景里倍增LCA已经是最平衡的选择既不慢也不难写。3.3 第三步按公式打标记预处理完成后读入每个操作(u, v)执行int t lca(u, v); diff[u] 1; diff[v] 1; diff[t] - 1; if (fa[t][0]) diff[fa[t][0]] - 1; // 点差分如果是边差分则把最后两行替换为diff[u] 1; diff[v] 1; diff[t] - 2;注意这里的判断条件点差分时如果lca是根节点它的父亲不存在diff[parent(lca)] - 1就要省略。很多不假思索照抄公式的选手会在这里越界。同理边差分的diff[t] - 2不需要判断父亲因为边差分本来就不涉及lca的父亲边。如果你想把所有操作合并统计甚至可以把标记数组合并成一个long long数组因为覆盖次数可能累加很大。遇到m1e5、每步加1的题最坏情况下路径上的点会被覆盖1e5次int是扛得住的但如果有每步加一个大于1的权值这种操作直接开long long更加稳妥免得最后溢出功亏一篑。3.4 第四步后序DFS汇总最后这一步是整个算法的精髓。遍历整棵树对每个节点u它的最终值 diff[u] 所有子节点最终值的和。这个加和过程其实就是在做树上前缀和。void dfs_sum(int u, int father) { for (int v : g[u]) { if (v father) continue; dfs_sum(v, u); diff[u] diff[v]; } // 此时diff[u]就是u的答案点差分或者u代表的那条边的答案边差分 }这个函数看起来简单但背后蕴含的道理值得想清楚为什么后序累加能把标记传播到路径上正确的节点集合因为标记原本只作用于端点通过子节点向父节点累加的过程标记会沿着树边逐层上移直到被某个负标记抵消或者一路传到根。这和一维差分的前缀和的思想高度一致——不同的只是扫描方向变成了树的拓扑方向。这里还有一个性能优化点如果树特别深或者递归开销大可以把dfs_sum改成迭代后序遍历用一个栈维护访问序。但坦白讲我写了几年竞赛题只要不是链状毒瘤数据递归版一直都是稳的。完整的框架如下可以直接作为做题的骨架使用#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOG 18; vectorint g[MAXN]; int depth[MAXN], fa[MAXN][LOG]; long long diff[MAXN]; void dfs_lca(int u, int father) { ... } // 预处理深度和倍增表 int lca(int u, int v) { ... } // 查询LCA void dfs_sum(int u, int father) { ... } // 后序累加 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 读入n, m和树边 // dfs_lca(root, 0) // 处理m个操作打标记 // dfs_sum(root, 0) // 输出diff[i]作为答案 return 0; }4. 经典题型逐一击破哪些题在考树上差分掌握了模板下面我们看几类真正会在CSP-S里出现的题型。你会发现树上差分的应用远不止给路径加1、最后输出这么简单许多看着毫无头绪的题目本质都在考这个套路。4.1 路径覆盖计数无脑板子题最基础的题型给你一棵树和若干条路径问每个点或每条边被多少条路径覆盖。这种就是纯模板按上面的框架直接做。今年或者明年的CSP-S如果出一道普及组难度的树上题很可能就是这样。做题的时候有一个关键的转化思维覆盖次数不一定是字面意义的覆盖也可以变成累计次数、通过次数、价值之和等。核心都是只要能定义清楚路径上的每个元素被额外贡献了某值就一定能用树上差分统计。举个例子如果把路径上每个点加1改成路径上每个点加上当前操作编号即第i次操作给路径上的点权增加i该怎么做直接改一下标记就行diff[u] i; diff[v] i; diff[t] - i; diff[fa[t][0]] - i。因为差分是线性运算加权的修改完全可以叠加统计。这一点扩展非常实用很多选手会在考场上忘了差分支持带权累加。4.2 边覆盖次数与最小割计数的转化有一类经典题给出一棵树有若干对点需要通信比如在树上铺设管道每一对的路径都需要被监控问哪种边被最多的路径需求覆盖。这是边差分的直接应用基本上就是板子题的换皮。还有个更有意思的转化给定一棵树和一些路径问有多少条路径覆盖了指定的一条边或者有几条边被所有路径同时覆盖。后者其实就是所有路径覆盖次数等于路径总数的边。做法是先边差分统计覆盖次数遍历一遍看谁等于路径总数。这种题目看起来像是在考集合交集实际上还是在跑板子。这里我强烈建议做练习的时候多动手画图。比如拿一棵5个节点的树随机指定两三条路径手动在纸上推一遍差分标记再用程序验证结果。我教过的同学里凡是动手推过的几乎没有在公式上再出过错凡是一上来就背公式的十有八九在lca那四个标记上栽跟头。4.3 树上最短路必经之路问题再来一道稍微绕一点的题给一棵树若干次询问访问路径问某一节点被经过了多少次。比如某人从u出发到v中途经过了多少个节点属于集合S或者访问所有指定路径时每个点被经过的总次数。这类问题通通可以抽象成给路径打标记统计点覆盖次数。它背后的思维是——路径信息可以通过端点和LCA的组合来完整表达。这恰好是树上差分最核心的建模思想。你可能会问如果路径有很多且每次还要查区间、求最大值呢那就要考虑树剖线段树来动态维护了。但请注意一个前提如果所有操作都是离线给出、最后只查一次总结果那么差分永远是最优的——复杂度O((nm)logn)代码量最小。只有当你需要在操作过程中动态查询在线查询时差分才不适用得请出树剖这种带数据结构的硬家伙。在CSP-S考场上识别离线这个特性往往比学会某个复杂数据结构更有价值。4.4 结合二分答案的最值问题树上差分还经常和二分答案组队出场。典型题目长这样给定一棵树有若干对点需要连边即沿树上路径走通现在你可以最多选择K条边使得每条边的覆盖次数不超过某个上限求最小的可能上限或者反过来求至少需要砍掉几条边才能阻断所有指定路径。这类题目的标准做法是二分答案树上差分判断。具体来说二分覆盖次数上限的限制值然后在check函数里检查每条边的覆盖次数是否都满足条件。覆盖次数用边差分统计复杂度O((nm)logn)再乘上二分次数logV总的复杂度O((nm)logn logV)在nm1e5的范围内稳过。我第一次接触这种组合套路的时候很震撼差分只是一个统计工具但它作为快速检查器嵌到二分框架里能解决的不等式约束问题远不止求覆盖次数这么简单。所以学树上差分不要浅尝辄止多琢磨它还能在当前算法中扮演什么角色。为了帮你快速判断题目是否在考树上差分我整理了一个简单的识别表题面特征推荐解法为什么树上路径批量修改最后一次性统计树上差分离线路径覆盖统计复杂度最低路径修改在线单点查询树剖线段树需要动态查询差分无法实现动态统计每条边被路径覆盖次数边差分边用子节点代表直接套板子树上路径问题可行性判断最大值最小二分树上差分差分负责快速check覆盖系数修改操作数量极大但只问一次树上差分常数小、实现简单、绝对不超时问每个点被经过的总次数点差分经过即路径覆盖本质相同5. 考场实战卡常、防爆栈与常见坑位避雷纸上谈兵到此为止接下来聊聊实战中那些让你掉分的小细节。这些教训都是我在模拟赛和真题里一个个踩出来的。5.1 递归与爆栈前面提过链状树的递归深度问题这里我再展开讲讲。竞赛Linux环境下默认的栈空间通常有8MB有的版本更多递归10^5层不一定每次都爆但如果你的DFS函数里有大数组或递归里开了太多临时变量就很容易栈溢出。三个解决办法第一编译时加大栈-Wl,--stack268435456但这在竞赛环境不一定总能行因为有些评测系统不允许你改编译选项。第二用一个显式的栈做DFS模拟后序遍历代码量会多出二三十行但绝对安全。第三如果确定树的形状比较健康深度在O(logn)级别比如随机树或者题目保证树是平衡的那就放心递归。说实话面对CSP-S这种压力环境我更推荐先写好递归版然后在代码开头加上一句ios::sync_with_stdio(false); cin.tie(nullptr);减少IO压力其他不折腾。等赛后复盘时再去测极限数据看看会不会爆栈心里有数即可。5.2 LOG的大小与动态规划LOG的大小是个隐患。for (int i 1; i LOG; i) fa[u][i] fa[fa[u][i-1]][i-1];这行代码能不能跑对取决于LOG是否大于树的深度。n1e5时LOG17理论上够但树上深度可能恰好大于2^17吗不会1e5以内的深度不可能超过1e52^171310721e5所以LOG17是够的。但如果你未来遇到n2e5的题LOG就必须至少18。我的习惯是直接定义成动态的LOG ceil(log2(n)) 1保险而且心安。还有一个小问题当n特别小比如n1DFS和LCA函数会不会越界会。所以你的代码开头最好特判一下n1的情况毕竟树的n2时才能保证边存在但部分题目会给单点树的边界数据。考场上多一点免疫意识就能少一次WA。5.3 标记的语义正确性做点差分时有人会问为什么不直接在diff[lca] - 2答案前面说过点差分光减两次不行——因为lca自己也要被覆盖被重复计算的只是lca位置的重复部分和向父节点的继续传播部分。这里你只要牢记一件事点差分中lca是路径成员边差分中lca对应的那条父边不是路径成员。语义正确公式就不会错。还有一道易错题如果修改的路径恰好就是根到一个点即lca是其一端点会不会多减不会。比如urootv某个节点lcarootdiff[parent(root)]不存在按模板判断省略即可标记变成diff[root] 1, diff[v] 1, diff[root] - 1即只diff[v]1。路径从根到v每个点都加1最终根的值 diff[root] 所有子节点的累加。因为子节点值向上汇入后根也会1完全正确。多推几遍这种特殊情况考场上才不会心里发虚。5.4 IO优化与long long有选手问nm1e5printf/scanf不是也很快吗确实C的scanf/printf足够快但用了cin/cout就必须关同步否则超时概率极大。另外如果你的答案要输出每个点的覆盖次数且m特别大比如1e6级别建议答案类型用long long。注意整型溢出的一个隐蔽场景diff数组统计的是累加标记值它的绝对值可大可小因为有正有负如果一路累加可能超过int范围用long long一劳永逸。5.5 调试三板斧树上差分的调试和其他图论算法不太一样推荐三个定位手段。第一小数据手算验证。构造一棵n5或n6的小树随机选择两三条路径手动推一遍答案再用程序输出diff数组对比每一步。第二打印中间量。在打标记那一步输出当前所有diff[u]在dfs_sum之后输出最终值对照公式推导很容易发现是LCA算错还是标记少写。第三对拍。如果某道题有暴力解法比如DFS直接模拟每条路径的覆盖就写个暴力版和差分版对拍。随机生成小树和操作跑几千组数据保证两个程序输出完全一致。对拍真的是图论题的救命稻草覆盖面之广超过任何人的直觉。6. 进阶思考树上差分的思想能延伸到哪里最后聊点轻松的进阶内容算是开胃菜。树上差分本质上是把区间信息编码到端点这个思想在非树形结构上也成立。比如二维平面上处理矩形区域覆盖可以用二维差分四个端点编码处理数组上区间计数支持斜率优化也可以用差分思想。CSES题单里有一道树上覆盖的题就是把点差分和二分结合到极致刷完那道题你对树上差分的理解会再上一个大台阶。还有一个延伸如果把路径换成一棵子树的加和操作树上差分就变成了子树差分——给某个点为根的整个子树都加v只需diff[u]v然后正常后序累加整个子树都会加上v。这个思维可能就一句话但在考场上能解掉不少看似需要高级数据结构实际只需要一行标记的题。我最后一次使用树上差分是在一场某校的校际模拟赛里题目给出一棵带边权的树和很多组限定时速路径要求统计每条边被重载的次数。直接用边差分十分钟写完交上去AC的那一刻我忽然很好笑地想起当年第一次写树剖调试两百行代码的样子。很多时候竞赛拼的不是谁的数据结构更高端而是谁能把最简单的工具用到极致。希望这篇文章能把树上差分这颗小巧而致命的子弹装进你的弹药库。下次在CSP-S考场外如果你看到有人对着树形图画箭头、标正负号不要惊讶——他大概率正在推导树上差分的标记公式。画多了公式就是你身体的一部分想忘都忘不掉。
