树上差分建立在差分数组的基础上，所以还不会差分数组的大佬可以先预习一下这篇博客，期望阅读时间
5
分钟：
差分数组
。
引入这样一个例题，给定一棵
n(n≤10
5
)
个点的树，
m(m≤10
5
)
次操作，将这棵树上的两点之间的最短路径上的每一个点都加
k
或者都减
k
，在这
m
次操作之后求出每个点的值。
首先，在你没有学过树上差分的时候，你会想到用倍增或者是塔尖求出这两个点的
LCA
然后暴力更改，显然这样每一次操作时间复杂度最劣会是
O(n)
，显然不能接受。
那么我们现在引入树上差分。
树上差分我们可以先感性的理解为树上的差分数组。
树上差分分为两种，一种是边的差分，另一种是点的差分。
那么今天我们就先来讲一下点的差分。
大家现在一定会想像差分数组从前往后扫一样从根往下扫，每个点存它与它的父亲的差，但是认真想一下，这样会存在一个问题，如果我将一条路径上每个点的值都增加k，那么这条路径上的其它枝杈都要打标记减去k。
如图：
这样当路径上的枝杈过多时，时间复杂度会非常不优。
那么应该怎么办呢？我们思考一下刚开始学
OI
的时候学到的递归思想来解决这个问题。
那么现在我们定义一个节点
u
的差分数组
B[u]
表示它与它所有儿子的加和的差，那么问题就变得简单多，我们只需要在最后统计答案的时候递归处理即可。
那么相比很多人有些疑惑，我们应该怎么做修改呢？
还是那个问题，现在我们要将两个点的最短路径上的点都加
k
或者减
k
，暂且设这两个点为
u
，
v
。
那么我们还需要再定义两个点，
u
和
v
的
LCA
为
lca
（倍增或塔尖求出），
lca
的直接父亲为
father
。
那么我们在更改的时候只需要做如下操作：
B[u]+=k;
B[v]+=k;
B[lca]-=k;
B[father]-=k;
那么为什么这么做是正确的呢？
我们可以认为我们在给
u
节点的差分数组
+k
的时候也就相当与将
u
到根的所有节点都加了
k
，给
v
节点的修改同理。
那么我们需要将多更改的部分减去，多更改的部分也就是
lca
多更改了一次，从
father
到跟节点多更改了两次，所以我们在将
B[lca]-=k,B[father]-=k
同时就相当于是做了这个操作（
B[lca]-=k
相当与减掉了
lca
多更改的那一次和
father
到跟节点多更改的一次，
B[father]-=k
相当于是剪掉了
father
到跟节点多更改的剩下的那一次，叠加即为减去了多更改的部分）。
当所有的操作都完成后只需要
DFS
递归统计答案即可。
如果你觉得你已经学会了树上差分，那么可以跳转这道例题（博客还没有写出来额）
rp++
转载于:https://www.cnblogs.com/wzc521/p/11032383.html