树上差分
据说近几年 NOIp 考得比较多，于是去研究了一下，做点笔记
树上前缀和:
说到差分就不得不说到前缀和 (因为两个互为逆操作). 对于树上差分， 我们需要定义一个类似前缀和的操作来将差分转化为原来的值
定义树上某个结点的前缀和为它本身及其所有后代结点的权值之和
(为什么这样定义？也许是好算吧…)
树上差分:
说完树上前缀和，进入正题
差分一般是用来做区间修改的，而树上差分也是一个道理
这里树上的” 区间” 指的其实是一条树链
我们可以对每个树上的结点定义一个数 d, 表示某个结点与它所有子结点的权值之和的差，叶子结点的 d 即为它本身
定义了 d 之后，我们就可以和序列一样， 把树上” 区间” 的操作转化为单点的操作.
比如上图，我们如果要把 4~8 的路径上的所有结点的权值加上 1, 那么对于 d 来说则是 \(d_8+1,d_1-1\)
同理，如果要把 1~7 的路径上的所有结点权值加 3, 对应 d 的操作则是 \(d_7+1,d_0-1\) (假设 1 的父节点是 0)
我们可以记录下 d 的改变量 , 当需要询问某个点改变后的权值时， 可以直接用 dfs 求该结点的 d 改变量的前缀和 (即它本身权值的改变量)
应用：
一般来说，涉及树上差分的题目一般是对于每两个点间的简单路径进行修改， 所以做这类题时首先要学会怎么求两点的 LCA.
一般这类问题分为两种：点的修改和边的修改
点的修改:
还是拿上图举例，假如我们需要将 5~6 之间的简单路径上的点的权值加上 1, 它们的 LCA 是 2, 我们可以把这条简单路径拆分为两条树链: 2~5 和 2~6
首先对 2~5 进行操作，即 \(d_5+1,d_1-1\);
然后对 2~6 进行操作，即 \(d_6+1,d_1-1\);
然后我们对 2 结点重复加了一次，需要减掉一次，操作即为 \(d_2-1,d_1+1\);
最终所做的更改为: \[d_5+1,\ d_6+1,\ d_2-1,\ d_1-1\]
由这个例子可以看出，对于树上的某两个点 u,v, 如果要对他们两个之间的简单路径上的所有点权值加 k, 则对应 d 的操作为:
\[ d_u+k,\ d_v+k, \\ d_{LCA(u,v)}-k, \\ d_{father(LCA(u,v))}-k \] (假设 1 的父亲结点是 0)
边的修改:
首先，我们把树上的每一条边 (u,v) 的权值记录在这两个结点深度较大的结点上 (即结点的权值记录的是它连向自己父亲结点的边的权值) 这样， 对于边的操作就变为了对于点的操作.
继续拿上面那张图举例，假如我们要将 6~7 之间的简单路径上的边权加 1, 它们的 LCA 是 1, 我们依然可以把这条简单路径拆为两条树链: 1~6 和 1~7
根据前面的转化，我们对 1~6 的修改即为: \(d_6+1,d_1-1\);
对 1~7 的修改即为: \(d_7+1,d_1-1\);
最终修改为: \(d_6+1,d_7+1,d_1-2\);
由这个例子可以看出，对于对于树上的某两个点 u,v, 如果要对他们两个之间的简单路径上的所有边权值加 k, 做完如上转化后， 对应 d 的操作为:
\[d_u+k,\ d_v+k,\\ d_{LCA(u,v)}-2k\]