顾名思义，树上差分就是一个把差分搬到树上的 trick，可以解决一些树上的链问题。

前置知识：前缀和，LCA，树的存储与遍历。

树上差分

对询问进行差分

询问可以被差分的前提是，这个询问具有可减性，即具有逆运算。

比如说，询问链和是可以使用树上差分的，因为加法存在逆运算。

但是，询问链上 $\min$ 值是不能使用树上差分的，因为 $\min$ 运算没有逆运算。

设 $d_u$ 为从根节点到 $u$ 的答案，$lca$ 为 $u$ 和 $v$ 的最近公共祖先，$\operatorname{query}(u, v)$ 为 $(u, v)$ 链的答案，对询问进行差分的公式是 $\operatorname{query}(u, v) = d_u + d_v - d_{lca} - d_{fa_{lca}}$。

注意，上述公式针对信息在点上的情况，所以要保证 $lca$ 的答案只被减掉一次，信息在边上的情况不需要保证，公式为 $\operatorname{query}(u, v) = d_u + d_v - 2d_{lca}$。

例题

生活在树上（easy version）

生活在树上（hard version）

对修改进行差分

首先，我们回顾对序列区间修改进行差分的过程。

• 给你一个序列 $a$，每次对 $[l, r]$ 中的每个元素加 $x$，最后求出 $a$ 的每个元素。

考虑维护 $a$ 的差分序列 $b$，$b_i = a_i - a_{i - 1}$，而 $a_i = \sum_{j = 1}^i b_j$。每次修改，只有 $b_l = b_l + x$，$b_{r + 1} = b_{r + 1} - x$。最后对 $b$ 序列做前缀和即可还原 $a$ 序列。

然后，我们把它放到树上。

• 给你一棵树，节点 $i$ 有一个权值 $a_i$，每次对 $(u, v)$ 链的每个节点加 $x$，最后求出这棵树的每个节点的权值。

还是考虑维护 $a$ 的差分 $b$，可是这次不同，$b_i = a_i - \sum_{j \in \operatorname{son}(i)} a_j$。然后，$a_i$ 为 $i$ 子树内的 $b_i$ 之和。类似的，设，$lca$ 为 $u$ 和 $v$ 的最近公共祖先，每次修改，只有 $b_u = b_u + 1$，$b_v = b_v + 1$，$b_{lca} = b_{lca} - 1$，$b_{fa_{lca}} = b_{fa_{lca}} - 1$。最后对 $b$ 做子树和和即可还原 $a$ 序列。

对于维护的信息在边上的情况，修改时有一些区别，但是区别不大。

模板题：[USACO15DEC] Max Flow P

例题

[NOIP2015 提高组] 运输计划

[NOIP2016 提高组] 天天爱跑步