众所周知 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