树上差分

据说近几年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$$