企业官网建设流程全解析

• 信奥赛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]+=v，d[r+1]-=v。全部修改完成后，对差分数组做一次前缀和，就能还原出每个位置的实际值。

为什么要这么绕一圈？因为单点修改是O(1)的，区间修改如果暴力做是O(n)的，而差分把区间修改压缩成了两次单点修改，本质上是"把区间信息编码到端点里"。

树上差分做的是同一件事：把树上路径的修改压缩成少数几个点的标记修改，最后通过一次DFS（相当于树上的"前缀和"）还原每个点或每条边的真实值。理解了这个思想，树上差分的所有公式都不需要死记——它们全是"想办法把一个路径修改表达成端点标记"的自然结果。

这里有一个非常关键的类比：一维数组的前缀和是一个线性过程，从d[1]一路加到d[i]；树上的"前缀和"其实就是一个后序DFS，每个节点的真实值等于它的差分值加上所有子节点的真实值之和。我第一次想明白这一点的时候，感觉像是打通了任督二脉——树上差分和树上DP的根本思路其实是一致的：子树信息向上汇聚。

再看一维差分的正确性：区间[l, r]加v，为什么要在r+1处减回来？因为前缀和会把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到lca，lca到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被重复计算的两次，又阻止了信号继续向上传。

如果你把"边差分"和"点差分"并排对比，会发现逻辑其实是一致的：因为它们本质上都是对"树上若干段路径修改"做端点编码，只是编码的单位不同——点差分的"最小单位"是点，边差分的"最小单位"是边（也就是非根节点与父亲的绑定关系）。

以下是两者的对比，建议直接收藏：

记不住的时候不用硬背，画棵树，从u、v分别向根画箭头，在lca处观察哪里重叠、哪里需要截断，公式自然就出来了。

2.3 一条链上的直觉验证

理论说了这么多，我们用最简单的"一条链"来验证公式，比打一百行代码都管用。

假设树是一条链：1-2-3-4-5，根是1。现在要统计从2到4路径上所有点的覆盖次数，且每个点初始为0。按照点差分的公式，lca(2,4)=2，parent(2)=1，所以标记为：diff[2]+=1，diff[4]+=1，diff[2]-=1，diff[1]-=1。合并后diff[4]=1，diff[2]=0，diff[1]=-1，其他为0。

后序DFS累加：5的最终值 = diff[5]=0；4的最终值 = diff[4] + 5的值 = 1；3 = 0 + 4的值 = 1；2 = diff 2 + 3的值 = 1；1 = diff 1 + 2的值 = 0。结果2、3、4各覆盖一次，完全正确——路径恰好是2-3-4。

再看边差分，统计2到4的边覆盖。lca(2,4)=2，标记为diff[2]+=1，diff[4]+=1，diff[2]-=2，即diff[2]=-1，diff[4]=1。后序累加：4=1，3=1，2=(-1)+1=0，1=0。哪个节点值非零？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,--stack=268435456），或者干脆改成手动模拟栈的迭代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; vector<int> 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的常数不满意（树是n=1e5、操作m=1e5时，倍增完全够用），也可以换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数组，因为覆盖次数可能累加很大。遇到m=1e5、每步加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; vector<int> 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((n+m)logn)，代码量最小。只有当你需要在操作过程中动态查询（在线查询）时，差分才不适用，得请出树剖这种带数据结构的硬家伙。在CSP-S考场上，识别"离线"这个特性往往比学会某个复杂数据结构更有价值。

4.4 结合二分答案的最值问题

树上差分还经常和二分答案组队出场。典型题目长这样：给定一棵树，有若干对点需要"连边"（即沿树上路径走通），现在你可以最多选择K条边，使得每条边的覆盖次数不超过某个上限，求最小的可能上限；或者反过来，求至少需要砍掉几条边才能阻断所有指定路径。

这类题目的标准做法是二分答案+树上差分判断。具体来说，二分"覆盖次数上限的限制值"，然后在check函数里检查每条边的覆盖次数是否都满足条件。覆盖次数用边差分统计，复杂度O((n+m)logn)，再乘上二分次数logV，总的复杂度O((n+m)logn logV)，在n=m=1e5的范围内稳过。

我第一次接触这种组合套路的时候很震撼：差分只是一个"统计工具"，但它作为"快速检查器"嵌到二分框架里，能解决的不等式约束问题远不止"求覆盖次数"这么简单。所以学树上差分不要浅尝辄止，多琢磨"它还能在当前算法中扮演什么角色"。

为了帮你快速判断题目是否在考树上差分，我整理了一个简单的识别表：

5. 考场实战：卡常、防爆栈与常见坑位避雷

纸上谈兵到此为止，接下来聊聊实战中那些让你掉分的小细节。这些教训都是我在模拟赛和真题里一个个踩出来的。

5.1 递归与爆栈

前面提过链状树的递归深度问题，这里我再展开讲讲。竞赛Linux环境下，默认的栈空间通常有8MB（有的版本更多），递归10^5层不一定每次都爆，但如果你的DFS函数里有大数组或递归里开了太多临时变量，就很容易栈溢出。三个解决办法：

第一，编译时加大栈：-Wl,--stack=268435456，但这在竞赛环境不一定总能行，因为有些评测系统不允许你改编译选项。第二，用一个显式的栈做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是否大于树的深度。n=1e5时LOG=17理论上够，但树上深度可能恰好大于2^17吗？不会，1e5以内的深度不可能超过1e5，2^17=131072>1e5，所以LOG=17是够的。但如果你未来遇到n=2e5的题，LOG就必须至少18。我的习惯是直接定义成动态的：LOG = ceil(log2(n)) + 1，保险而且心安。

还有一个小问题：当n特别小（比如n=1），DFS和LCA函数会不会越界？会。所以你的代码开头最好特判一下n=1的情况，毕竟树的n>=2时才能保证边存在，但部分题目会给单点树的边界数据。考场上多一点免疫意识，就能少一次WA。

5.3 标记的语义正确性

做点差分时，有人会问：为什么不直接在diff[lca] -= 2？答案前面说过，点差分光减两次不行——因为lca自己也要被覆盖，被重复计算的只是lca位置的重复部分和向父节点的继续传播部分。这里你只要牢记一件事：点差分中，lca是"路径成员"；边差分中，lca对应的那条父边不是"路径成员"。语义正确，公式就不会错。

还有一道易错题：如果修改的路径恰好就是根到一个点（即lca是其一端点），会不会多减？不会。比如u=root，v=某个节点，lca=root，diff[parent(root)]不存在，按模板判断省略即可，标记变成diff[root] += 1, diff[v] += 1, diff[root] -= 1，即只diff[v]+=1。路径从根到v，每个点都加1，最终根的值 = diff[root] + 所有子节点的累加。因为子节点值向上汇入后，根也会+1，完全正确。多推几遍这种特殊情况，考场上才不会心里发虚。

5.4 IO优化与long long

有选手问：n=m=1e5，printf/scanf不是也很快吗？确实，C++的scanf/printf足够快，但用了cin/cout就必须关同步，否则超时概率极大。另外，如果你的答案要输出每个点的覆盖次数，且m特别大（比如1e6级别），建议答案类型用long long。注意整型溢出的一个隐蔽场景：diff数组统计的是"累加标记值"，它的绝对值可大可小（因为有正有负），如果一路累加可能超过int范围，用long long一劳永逸。

5.5 调试三板斧

树上差分的调试和其他图论算法不太一样，推荐三个定位手段。

第一，小数据手算验证。构造一棵n=5或n=6的小树，随机选择两三条路径，手动推一遍答案，再用程序输出diff数组，对比每一步。第二，打印中间量。在打标记那一步，输出当前所有diff[u]，在dfs_sum之后，输出最终值；对照公式推导，很容易发现是LCA算错还是标记少写。第三，对拍。如果某道题有暴力解法（比如DFS直接模拟每条路径的覆盖），就写个暴力版和差分版对拍。随机生成小树和操作，跑几千组数据，保证两个程序输出完全一致。对拍真的是图论题的救命稻草，覆盖面之广超过任何人的直觉。

6. 进阶思考：树上差分的思想能延伸到哪里

最后聊点轻松的进阶内容，算是开胃菜。

树上差分本质上是"把区间信息编码到端点"，这个思想在非树形结构上也成立。比如二维平面上处理矩形区域覆盖，可以用二维差分（四个端点编码）；处理数组上"区间计数支持斜率优化"，也可以用差分思想。CSES题单里有一道"树上覆盖"的题，就是把点差分和二分结合到极致，刷完那道题，你对树上差分的理解会再上一个大台阶。

还有一个延伸：如果把"路径"换成一棵子树的加和操作，树上差分就变成了"子树差分"——给某个点为根的整个子树都加v，只需diff[u]+=v，然后正常后序累加，整个子树都会加上v。这个思维可能就一句话，但在考场上能解掉不少"看似需要高级数据结构实际只需要一行标记"的题。

我最后一次使用树上差分是在一场某校的校际模拟赛里，题目给出一棵带边权的树和很多组"限定时速路径"，要求统计每条边被"重载"的次数。直接用边差分十分钟写完，交上去AC的那一刻，我忽然很好笑地想起当年第一次写树剖调试两百行代码的样子。很多时候，竞赛拼的不是谁的数据结构更高端，而是谁能把最简单的工具用到极致。

希望这篇文章能把树上差分这颗"小巧而致命的子弹"装进你的弹药库。下次在CSP-S考场外，如果你看到有人对着树形图画箭头、标正负号，不要惊讶——他大概率正在推导树上差分的标记公式。画多了，公式就是你身体的一部分，想忘都忘不掉。