虚树

简介

虚树一般用于 树形DP 中，可以有效减少冗余的计算量。

其原理是将对 DP 无影响，或者在影响可快速运算范围内的点缩在一起，从而使得整棵树大小极大的减小。

因此，可以使用虚树的题目一般有 特殊点 之类的设定，多测并限定 特殊点 的总量。

P2495 [SDOI2011] 消耗战

一道经典的虚树题。

如果要考虑虚树，我们需要先考虑原树上是如何 DP 的。

DP

设 \(f(u)\) 表示切断 \(u\) 子树中所有能源所需要的代价。

记 \(v\) 表示 \(u\) 的儿子，\(w\) 为 \(u\) 到其父亲的边权。

若 \(u\) 有能源：

直接切断 \(u\) 到父亲的桥梁。

若 \(u\) 无能源：

虚树

接下来考虑有哪些点可以省去。

观察状态转移方程，能源点肯定需要保留，能源点两两之间的 LCA 也需要保留。

即如图若加粗的点为能源点，则 5，2，1，都需要保留。