2022.11.05

P5024

这题在任务栏里摆了一周终于A了。。。
只能说写的挺扭曲的，但还好过了。
做法：用倍增数组处理状态，然后在询问时分类讨论两点是否在一条链上，最后用倍增数组快速模拟一遍状态转移过程求出每一次的答案。
这题的状态设计十分智慧，用 \(f_{i,j,1/0,1/0}\) 来表示 \(i\) 的 \(2^j\) 级祖先的子树去掉 \(i\) 的子树的最小花费，且 \(i\) 节点取/不取，\(i\) 的 \(2^j\) 级祖先取/不取（\(1\) 为取 \(0\) 为不取）（抄的参考的这篇题解）。这样一来在更新答案的时候就可以像鱼骨头的结构一样一层层往上叠加，以求出最后的答案了。
总之就挺毒瘤的，有点细节，但其实打起来还好，没有调很久。

原文地址：http://www.cnblogs.com/cotsheep/p/16859917.html