本文使用树链剖分维护一类动态的树形动规问题。
也可以参考immortalco的文章。
我们曾经做过一类动态序列动规问题，也就是将静态的序列问题放在线段树上维护。
不妨将其推广到树上，使用树链剖分来维护动态的树形动规问题。不妨再将其推广到仙人掌上。
重链剖分与可合并$tag$
既然是树链剖分，首先将转移方程拆分成与重儿子有关的式子和与重儿子无关的式子。
如洪水的方程：
拆分为：
将$(a,b)$二元组视为一个$tag$，其满足结合律，也就是可合并：
目前遇到的$tag$出现了这样的多元组变换与矩阵变换的形式。
当然不排除还会有其他形式，只要是可合并的$tag$即可。
然后考虑使用线段树维护$tag$。
$tag$的合并
接下来我们会用到这些变量/数组：
- $tag$：线段树维护的属性。
- $f$：树形动规数组。
- $restf$：轻儿子的$f$的复合。
对于每一条重链$l\rightarrow r$，我们维护一个线段树来处理其值。
线段树每个结点$[x,r]$包含一个$tag$，表示链底的虚拟儿子结点（并不实际存在，理想的作为单位元的儿子）的$f$值（在洪水题中为$0$）经过$tag$变换后可以得到$x$的$f$值。
因为单位元是固定的，因此通过$tag$可以直接得到$f$值。
因此我们只需要维护线段树每个结点的$tag$即可。
因为$tag$有可合并性，故线段树可以直接合并，注意合并顺序为从右往左合并（从深往浅合并）。
预处理重链的$tag$
将重链按照链顶深度排序，从最深的重链开始合并。
每次建出当前重链的线段树，将其$f$合并到链顶父亲的$restf$中（$restf$代表轻链的$f$和）。
这样，其父亲建立线段树时又会通过$restf$预处理$tag$。
如此重复，最终即可预处理完所有重链的$tag$。
处理修改
修改与预处理类似。
找到需要修改的点，更新链顶$t$的$restf$，消除原有$restf$对$father[t]$的影响，添加新的$restf$的影响，如此不断重复迭代到最顶层。
取出$f(x)$的值
找到对应重链，提取出线段树上$[x,r]$的$tag$，通过单位元复合$tag$计算$f(x)$。
细节
- 在修改与预处理的时候，需要先消除原有的影响，再加上新的影响。
在某些情况下，原有的影响需要事先爬一遍树记录下来，不能爬的时候一边修改一边查询。 - 在叶子结点的时候没有选择子树的权利，可能需要特判一下。
- 合并$tag$的时候需要从深往浅合并。
- 若$tag$是一个向量，将整个向量一起放在线段树中处理会比在外部枚举向量元素，在线段树中一个一个处理快很多。
