「两只 log 的动态 DP」学习笔记

众所周知 NOIP2018 D2T3 出了一道标算是倍增的动态 DP 模板题……
于是复习 CSP-S 的我就跑过来学了。

题意:
给定一棵 \(n\) 个结点的树,点 \(i\) 有点权 \(a_i\)(原题为 \(p_i\))。
\(m\) 次询问,每次询问要求求出强制选择 / 不选择某两个点的最小点覆盖。
\(n = m \le 10^5\)

考虑一个简化版的问题:只询问一次,不强制钦点任何点。
典型树形 DP,可以发现这个题和最大独立集有异曲同工之妙(其实最小点覆盖 = 点权和 - 最大独立集,随手证)。
\(f_{u,0/1}\) 表示选 / 不选 \(u\) 这个点的情况下,以 \(u\) 为根子树内的最小点覆盖。
有转移 \[ \begin{align*} f_{u,0}=&\sum\limits_{(u,v)\in E} f_{v,1} \\ f_{u,1}=&a_u+\sum\limits_{(u,v)\in E} \min(f_{v,0},f_{v,1}) \end{align*} \]

考虑一条链的情况(\(E=\{(i,i+1) \mid 1\le i<n\}\)):
转移就变成了 \[ \begin{align*} f_{u,0}=&f_{u+1,1} \\ f_{u,1}=&a_u+\min(f_{u+1,0},f_{u+1,1}) \end{align*} \]

注意到这个式子有点太过简洁了(
考虑重新定义矩阵乘法,即将乘法换成加法,加法换成 \(\min\)
此处把这种运算写作 \(\otimes\)。 即 \[C_{i,j} = \min\limits_{k}(A_{i,k}+B_{k,j})\]

则容易发现这个运算仍然满足结合律。

考虑用这个运算描述转移。
\[ \begin{bmatrix} \infty&0\\ a_u&a_u \end{bmatrix} \otimes \begin{bmatrix} f_{u+1,0}\\ f_{u+1,1} \end{bmatrix}= \begin{bmatrix} f_{u,0}\\ f_{u,1} \end{bmatrix} \]

序列上的搞定了,那么放到树上就轮到树剖了!(逃
然鹅这个好像不是很好维护?
考虑利用树剖的性质,将轻重儿子分类讨论(这就是链分治)。
\(g_{u,0/1}\) 是不考虑 \(u\) 的重儿子情况下的 \(f\)
\[ \begin{align*} f_{u,0}=&g_{u,0}+f_{\text{son}_u,1} \\ f_{u,1}=&g_{u,1}+\min(f_{\text{son}_u,0},f_{\text{son}_u,1}) \end{align*} \]

发现和刚才的形式差不多?
照样写成 \(\otimes\) 的形式: \[ \begin{bmatrix} \infty&g_{u,0}\\ g_{u,1}&g_{u,1} \end{bmatrix} \otimes \begin{bmatrix} f_{\text{son}_u,0}\\ f_{\text{son}_u,1} \end{bmatrix}= \begin{bmatrix} f_{u,0}\\ f_{u,1} \end{bmatrix} \]

然后随便维护一下就好了。

现在来考虑强制钦定某个点的选择情况。
注意到若强制选择 \(u\),相当于令 \(g_{u,0}=\infty\)
反之即为 \(g_{u,1}=\infty\)
故只需要能够动态更新 DP 值即可。

注意到非重链顶的 \(f\) 没啥用,可以直接一路 \(\otimes\) 上去。
于是可以每次跳到链顶,更新 \(f\),由此更新父亲的 \(g\),然后接着跳。

然后就做完了。

代码见 https://www.alpha1022.me/articles/loj-2955.htm