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

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

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

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

考虑一条链的情况(E={(i,i+1)1i<n}E=\{(i,i+1) \mid 1\le i<n\}):
转移就变成了

注意到这个式子有点太过简洁了(
考虑重新定义矩阵乘法,即将乘法换成加法,加法换成 min\min
此处把这种运算写作 \otimes。 即

Ci,j=mink(Ai,k+Bk,j)C_{i,j} = \min\limits_{k}(A_{i,k}+B_{k,j})

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

考虑用这个运算描述转移。

[0auau][fu+1,0fu+1,1]=[fu,0fu,1] \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}

序列上的搞定了,那么放到树上就轮到树剖了!(逃
然鹅这个好像不是很好维护?
考虑利用树剖的性质,将轻重儿子分类讨论。
gu,0/1g_{u,0/1} 是不考虑 uu 的重儿子情况下的 ff

发现和刚才的形式差不多?
照样写成 \otimes 的形式:

[gu,0gu,1gu,1][fsonu,0fsonu,1]=[fu,0fu,1] \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}

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

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

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

然后就做完了。

代码见