本文主要是介绍【NOIP2018】洛谷5024 保卫王国，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解法一
把强制选或者不选点看成对权值的修改，转化成动态最大权独立集问题。
树链剖分， f i f_i fi表示 i i i子树的最大权独立集， g i g_i gi表示 i i i子树强制不取 i i i的最大权独立集。 s f i , s g i sf_i,sg_i sfi,sgi表示 i i i轻儿子 f , g f,g f,g的和。如果 u u u是 v v v的重儿子，转移方程为
g v = s f v + f u f v = max ( s f v + f u , p v + g u + s g v ) g_v=sf_v+f_u \\ f_v=\max(sf_v+f_u,p_v+g_u+sg_v) gv=sfv+fufv=max(sfv+fu,pv+gu+sgv)
把加法类比成乘法，取最大值类比成加法，转移方程可以看成是从 [ g u f u ] \left[\begin{matrix} g_u \\ f_u\end{matrix}\right] [gufu]到 [ g v f v ] \left[\begin{matrix} g_v \\ f_v\end{matrix}\right] [gvfv]的线性变换，因此满足结合律，可以用线段树维护变换矩阵。修改操作也是和树链剖分一样在轻重链上跳。
解法二
对结点 i i i记录它的子树和头顶上的部分可以选它或强制不选它的最小代价。再维护倍增数组记录祖先的子树中不属于 i i i子树的部分的信息。对于询问从两个点往上倍增求解。
参考文献
immortalCO . NOIP2018 D2T3 题解 + 关于动态 DP 等科技的一些总结 . http://immortalco.blog.uoj.ac/blog/4650
immortalCO . 基于变换合并的树上动态 DP 的链分治算法 & SDOI2017 切树游戏（cut）解题报告 . http://immortalco.blog.uoj.ac/blog/2625
zhoutb2333 . 题解 P5024 【保卫王国】 . https://www.luogu.org/blog/zhoutb2333/solution-p5024
这篇关于【NOIP2018】洛谷5024 保卫王国的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
