动态DP小记

标签：重链 max son 子树 DP 动态 dp 小记

前言

矩阵乘法优化DP，重链剖分。

涉及到的知识点是比较复杂的，但是比较重要。

这是猫锟在 WC2018 讲的黑科技，一般用来解决树上的带有点权（边权）修改操作的 DP 问题，为了普及，甚至 CSP2022-S T4 考到了此知识点。

做法

朴素DP

设 \(dp_{i,0}\) 表示不选 \(i\)，\(i\) 的子树的最大权独立集的权值大小。
\(dp_{i,1}\) 表示选 \(i\)，\(i\) 的子树的最大权独立集的权值大小。
则有：

\[dp_{i,0}=\sum\limits_{x=1} \max\{dp_{x,0},dp_{x,1}\}\\ dp_{i,1}=\sum\limits_{x=1} dp_{x,0}+a_i \]

最后答案 \(ans=\max\{dp_{1,0},dp_{1,1}\}\)。

但显然，这个式子如果带修没法跑，复杂度会炸掉，要继续优化。

重链剖分

我们使用重剖优化带修的部分，可以在 \(\Theta(\log^2n)\) 的复杂度下实现单点修改。

将这棵树剖分后，假如有这样一条重链：

设 \(g_{i,0}\) 表示不选择 \(i\) 且只允许选择 \(i\) 的轻儿子所在子树的最大答案，

\(g_{i,1}\) 表示不考虑 \(son_i\) 的情况下选择 \(i\) 的最大答案，

\(son_i\) 表示 \(i\) 的重儿子。

则刚才的方程就简化为：

\[dp_{i,0}=g_{i,0}+\max\{dp_{son_i,0},dp_{son_i,1}\}\\ dp_{i,1}=g_{i,1}+dp_{son_i,0} \]

最后答案 \(ans=\max\{dp_{rt,0},dp_{rt,1}\}\)。

然后我们现在要考虑如何在线段树内 \(\Theta(1)\) 的修改与查询。

矩阵乘法

我们发现这可以用矩阵乘法优化。

标签：重链,max,son,子树,DP,动态,dp,小记
From： https://www.cnblogs.com/code-ac/p/17727863.html