动态 DP
动态 DP 问题是猫锟在 WC2018 讲的黑科技，一般用来解决树上的带有点权（边权）修改操作的 DP 问题．
例子
以这道模板题为例子讲解一下动态 DP 的过程．
给定一棵 𝑛n
个点的树，点带点权．有 𝑚m 次操作，每次操作给定 𝑥,𝑦x,y 表示修改点 𝑥x 的权值为 𝑦y．你需要在每次操作之后求出这棵树的最大权独立集的权值大小．
广义矩阵乘法
定义广义矩阵乘法 𝐴 ×𝐵 =𝐶A×B=C 为：
𝐶𝑖,𝑗=𝑛max𝑘=1(𝐴𝑖,𝑘+𝐵𝑘,𝑗)Ci,j=maxk=1n(Ai,k+Bk,j)
相当于将普通的矩阵乘法中的乘变为加，加变为 maxmax 操作．
同时广义矩阵乘法满足结合律，所以可以使用矩阵快速幂．
不带修改操作
令 𝑓𝑖,0fi,0 表示不选择 𝑖i 的最大答案，𝑓𝑖,1fi,1 表示选择 𝑖i 的最大答案．
则有 DP 方程：
{𝑓𝑖,0=∑𝑠𝑜𝑛max(𝑓𝑠𝑜𝑛,0,𝑓𝑠𝑜𝑛,1)𝑓𝑖,1=𝑤𝑖+∑𝑠𝑜𝑛𝑓𝑠𝑜𝑛,0{fi,0=∑sonmax(fson,0,fson,1)fi,1=wi+∑sonfson,0
答案就是 max(𝑓𝑟𝑜𝑜𝑡,0,𝑓𝑟𝑜𝑜𝑡,1)max(froot,0,froot,1).
带修改操作
首先将这棵树进行树链剖分，假设有这样一条重链：
设 𝑔𝑖,0gi,0 表示不选择 𝑖i 且只允许选择 𝑖i 的轻儿子所在子树的最大答案，𝑔𝑖,1gi,1 表示不考虑 𝑠𝑜𝑛𝑖soni 的情况下选择 𝑖i 的最大答案，𝑠𝑜𝑛𝑖soni 表示 𝑖i 的重儿子．
假设我们已知 𝑔𝑖,0/1gi,0/1 那么有 DP 方程：
{𝑓𝑖,0=𝑔𝑖,0+max(𝑓𝑠𝑜𝑛𝑖,0,𝑓𝑠𝑜𝑛𝑖,1)𝑓𝑖,1=𝑔𝑖,1+𝑓𝑠𝑜𝑛𝑖,0{fi,0=gi,0+max(fsoni,0,fsoni,1)fi,1=gi,1+fsoni,0
答案是 max(𝑓𝑟𝑜𝑜𝑡,0,𝑓𝑟𝑜𝑜𝑡,1)max(froot,0,froot,1).
可以构造出矩阵：
[𝑔𝑖,0𝑔𝑖,0𝑔𝑖,1−∞]×[𝑓𝑠𝑜𝑛𝑖,0𝑓𝑠𝑜𝑛𝑖,1]=[𝑓𝑖,0𝑓𝑖,1][gi,0gi,0gi,1−∞]×[fsoni,0fsoni,1]=[fi,0fi,1]
注意，我们这里使用的是广义乘法规则．
可以发现，修改操作时只需要修改 𝑔𝑖,1gi,1 和每条往上的重链即可．
具体思路
- DFS 预处理求出 𝑓𝑖,0/1fi,0/1 和 𝑔𝑖,0/1gi,0/1.
- 对这棵树进行树链剖分（注意，因为我们对一个点进行询问需要计算从该点到该点所在的重链末尾的区间矩阵乘，所以对于每一个点记录 𝐸𝑛𝑑𝑖Endi 表示 𝑖i 所在的重链末尾节点编号），每一条重链建立线段树，线段树维护 𝑔g 矩阵和 𝑔g 矩阵区间乘积．
- 修改时首先修改 𝑔𝑖,1gi,1 和线段树中 𝑖i 节点的矩阵，计算 𝑡𝑜𝑝𝑖topi 矩阵的变化量，修改到 𝑓𝑎𝑡𝑜𝑝𝑖fatopi 矩阵．
- 查询时就是 1 到其所在的重链末尾的区间乘，最后取一个 maxmax 即可．
代码实现
---|---
## 习题
* [SPOJ GSS3 - Can you answer these queries III](https://www.spoj.com/problems/GSS3/)
* [「NOIP2018」保卫王国](https://loj.ac/p/2955)
* [「SDOI2017」切树游戏](https://loj.ac/p/2269)
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/dp/dynamic.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/dp/dynamic.md "edit.link.title")
> __本页面贡献者：[LJFYC007](https://github.com/LJFYC007), [c-forrest](https://github.com/c-forrest), [mgt](mailto:i@margatroid.xyz), [sshwy](https://github.com/sshwy), [StudyingFather](https://github.com/StudyingFather), [Tiphereth-A](https://github.com/Tiphereth-A), [CSPNOIP](https://github.com/CSPNOIP), [Early0v0](https://github.com/Early0v0), [Enter-tainer](https://github.com/Enter-tainer), [H-J-Granger](https://github.com/H-J-Granger), [Henry-ZHR](https://github.com/Henry-ZHR), [huhaoo](https://github.com/huhaoo), [Ir1d](https://github.com/Ir1d), [isdanni](https://github.com/isdanni), [kenlig](https://github.com/kenlig), [ksyx](https://github.com/ksyx), [Marcythm](https://github.com/Marcythm), [Mout-sea](https://github.com/Mout-sea), [NachtgeistW](https://github.com/NachtgeistW), [ouuan](https://github.com/ouuan), [thredreams](https://github.com/thredreams), [Xeonacid](https://github.com/Xeonacid)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用