前言
动态 DP 问题是猫锟在 WC2018 讲的黑科技，一般用来解决树上的 DP 问题，同时支持点权（边权）修改操作。
在 NOIP2018D2T3 考察后风靡 OI 圈。
一般来说 ，将 DP 的状态转移方程写成矩阵形式，随后通过修改矩阵来实现修改功能。
模板例题
给一棵带点权的树，求最大独立集大小。
定义 $f(u,0)$ 代表不选 $u$ 点，以 $u$ 为子树中最大权独立集的大小，$f(u,1)$ 为选择 $u$ 点的大小。
容易得到状态转移方程：
$$f(u,0) = \sum \limits _{v \in son_u} \max(f(v,0),f(v,1))$$
$$f(u,1) = w_u + \sum \limits _{v \in son_u} f(v,0)$$
到了修改部分。
对这棵树进行轻重链剖分，定义 $g(u,0)$ 为 $u$ 子树内不考虑重儿子，$u$ 点不选时的最大权独立集大小。
$$g(u,0) = \sum \limits _{v \in son_u,v \ne heavyson(u)} \max(f(v,0),f(v,1))$$
同样定义 $g(u,1)$ 为 $u$ 子树内不考虑重儿子，$u$ 点选择时最大权独立集大小。
$$g(u,1) = w_u + \sum \limits _{v \ in son_u,v \ne heavyson(u)} f(v,0)$$
那么加上重儿子贡献即可得到 $u$ 点状态，有：
$$f(u,0) = g(u,0) + \max(f(heavyson(u),0),f(heavyson(u),1))$$
$$f(u,1) = g(u,1) + f(heavyson(u),0)$$
可以假定 $g(u,0),g(u,1)$ 已知，稍微改写转移方程：
$$f(u,0) = \max(g(u,0) + f(v,0),g(u,0) + f(v,1))$$
$$f(u,1) = \max(-\infty,g(u,1) + f(v,0))$$
由重儿子状态可以推知当前点状态，并且可以写出转移矩阵：
$$\begin{vmatrix} g(u,0) & g(u,0)\ g(u,1) & -\infty \end{vmatrix} \times \begin{vmatrix} f(v,0) \ f(v,1) \end{vmatrix} = \begin{vmatrix}f(u,0) \ f(u,1)\end{vmatrix}$$
注意这里重定义了矩阵乘法，$C = A \times B,C_{i,k} = \max (A_{i,j} + B_{j,k})$.
满足结合律，可以用线段树维护一段矩阵相乘的结果，放到树上就是轻重链剖分套线段树。
可以发现，叶子结点的 $f$ 矩阵就是 $g$ 矩阵的左半部分，考虑如何查询答案。其实就是根节点所在的重链，从叶子节点的矩阵沿着重链一直乘到根节点的矩阵。
接下来思考修改会造成什么影响，修改 $x$ 点的点权首先会影响 $g(x,1)$
$$g(u,1) = w_u + \sum \limits _{v \ in son_u,v \ne heavyson(u)} f(v,0)$$
那么修改该位置即可，然而 $g(x,1)$ 变化后，还会影响到它上方的点。
与 $x$ 在同一条重链上的点，不用考虑影响，因为线段树的 pushup 已经维护好了。而再往上，就需要修改了。
考虑 $top[x]$ 是作为 $u$ 点的一个轻儿子来记贡献，现在 $f(top[x])$ 发生了变化，使得 $g(u)$ 也发生了变化，那么就需要修正 $u$ 点处的矩阵。
一条重链的尾部一定是叶子结点，因此可以记录每个重链的末端，直接利用线段树查询出 $f(top[x])$ 的值，随后对应地进行修改。
也就是，从 $x$ 点不断跳链跳到根节点。
然而实现相当多细节，比如说，矩阵乘法满足结合律而不满足交换律。
如果定义状态矩阵为 $1 \times 2$ 大小，那么就是：
$$(1,2) \times (2,2) = (1,2)$$
那么就需要逆序乘，即线段树右儿子乘上左儿子，才能保证从叶子结点向上推。
然而如果定义 $2 \times 1$ 大小，就有：
$$(2,2) \times (2,1) = (2,1)$$
那么就要先乘上转移矩阵，再乘上叶子结点的状态矩阵，也就是线段树左儿子乘上右儿子。
具体看代码吧，也不是很难打。
|
|
保卫王国
一道看起来很像板子题的东西。
最小覆盖集 = 全集 - 最大独立集
尽管可以利用这个转化为板子，但直接求最小覆盖集也是可行的。
定义 $f(u,0)$ 为 $u$ 为根的子树内，不选 $u$ 的最小代价，$f(u,1)$ 为选 $u$ 的最小代价。
$$f(u,0) = \sum f(v,1)$$
$$f(u,1) = \sum \min(f(v,0),f(v,1))$$
同样按照套路，轻重链剖分，定义 $g(u,0)$ 为除去重儿子外，不选 $u$ 的最小代价，$g(u,1)$ 为除去重儿子外，选 $u$ 的最小代价。
$$g(u,0) = \sum \limits _{v \ne son(u)} f(v,1)$$
$$g(u,1) = w_u + \sum \limits _{v \ne son(u)} \min(f(v,0),f(v,1))$$
改写状态转移方程，有：
$$f(u,0) = f(son,1) + g(u,0)$$
$$f(u,1) = \min(f(son,0) + g(u,1),f(son,1) + g(u,1))$$
接下来开始构造矩阵，按照线段树左儿子乘上右儿子的习惯，构造 $2 \times 1$ 的状态矩阵与 $2 \times 2$ 的转移矩阵。
$$\begin{vmatrix} +\infty & g(u,0) \ g(u,1) & g(u,1) \end{vmatrix} \times \begin{vmatrix} f(son,0) \ f(son,1) \end{vmatrix} = \begin{vmatrix} f(u,0) \ f(u,1) \end{vmatrix}$$
接下来按照套路，思考如何在修改时维护 $fa[top[x]]$ 的 $g$ 矩阵。
$$g(u,0) = \sum \limits _{v \ne son(u)} f(v,1)$$
$$g(u,1) = w_u + \sum \limits _{v \ne son(u)} \min(f(v,0),f(v,1))$$
简单的加加减减，没太大区别。
强制选点，强制不选点，只要修改转移矩阵即可。
如果强制选点，就让不选点的转移矩阵对应位置变成 $+\infty$，如果强制不选点，就让选点的对应位置变成 $+\infty$
为了方便撤销，可以不直接修改，而使用加上 $+\infty$ 的方法，撤销时减去 $+\infty$ 即可。
然而需要注意的是，此时的 $f$ 矩阵与 $g$ 矩阵形态不同了，需要特判叶子结点，并将 $f$ 矩阵塞到对应位置。
修改的时候，也同样需要特判叶子结点。
似乎也有规避这个特判的方法，就是改改矩阵形态，让它们恰好对正。不过不知道行不行，我直接硬上特判了。
|
|