icontofig | 发布于 2020-07-12 22:40:20 | 阅读量 193 | DP 虚树
发布于 2020-07-12 22:40:20 | DP 虚树
Luogu P2495 [SDOI2011]消耗战 虚树+树形DP
  题解本人的虚树入门题。 基础思想题目意思相当于m次询问,每次询问给出一些点,要我们付出一定代价断边使得给出的这些点与根节点1不连通. 首先肯定能确定这个题是一个树形DP。转移方程也非常好写。 考虑对于单次询问,我们设f[x]为处理完以x为子树的最小的代价。 那么转移无非是两种情况: 1.断开与父亲的连接,代价为从x到根1的路径上的最小值。 2.当该点不是询问点的时候,把子树内所有询问点都与根节点断开的代价。 但是这样有一个问题,每次询问都是O(n)的,来看一下数据范围: 很明显O(nm)的做法是无法处理的。 进阶优化 & 虚树的引出但实际上,我们在对每一次询问的处理中,
继续阅读