众所周知 NOIP2018 D2T3 出了一道标算是倍增的动态 DP 模板题……
于是复习 CSP-S 的我就跑过来学了。
题意：
给定一棵 n 个结点的树，点 i 有点权 ai（原题为 pi）。
有 m 次询问，每次询问要求求出强制选择 / 不选择某两个点的最小点覆盖。
n=m≤105。
考虑一个简化版的问题：只询问一次，不强制钦点任何点。
典型树形 DP，可以发现这个题和最大独立集有异曲同工之妙（其实最小点覆盖 = 点权和 - 最大独立集，随手证）。
设 fu,0/1 表示选 / 不选 u 这个点的情况下，以 u 为根子树内的最小点覆盖。
有转移 fu,0=∑(u,v)∈Efv,1fu,1=au+∑(u,v)∈Emin(fv,0,fv,1)
考虑一条链的情况（E={(i,i+1)∣1≤i<n}）：
转移就变成了 fu,0=fu+1,1fu,1=au+min(fu+1,0,fu+1,1)
注意到这个式子有点太过简洁了（
考虑重新定义矩阵乘法，即将乘法换成加法，加法换成 min。
此处把这种运算写作 ⊗。 即 Ci,j=mink(Ai,k+Bk,j)
则容易发现这个运算仍然满足结合律。
考虑用这个运算描述转移。
得 [∞0auau]⊗[fu+1,0fu+1,1]=[fu,0fu,1]
序列上的搞定了，那么放到树上就轮到树剖了！（逃
然鹅这个好像不是很好维护？
考虑利用树剖的性质，将轻重儿子分类讨论（这就是链分治）。
设 gu,0/1 是不考虑 u 的重儿子情况下的 f。
则 fu,0=gu,0+fsonu,1fu,1=gu,1+min(fsonu,0,fsonu,1)
发现和刚才的形式差不多？
照样写成 ⊗ 的形式： [∞gu,0gu,1gu,1]⊗[fsonu,0fsonu,1]=[fu,0fu,1]
然后随便维护一下就好了。
现在来考虑强制钦定某个点的选择情况。
注意到若强制选择 u，相当于令 gu,0=∞；
反之即为 gu,1=∞。
故只需要能够动态更新 DP 值即可。
注意到非重链顶的 f 没啥用，可以直接一路 ⊗ 上去。
于是可以每次跳到链顶，更新 f，由此更新父亲的 g，然后接着跳。
然后就做完了。
代码见 https://www.alpha1022.me/articles/loj-2955.htm