虚树
简介
虚树一般用于 树形DP 中，可以有效减少冗余的计算量。
其原理是将对 DP 无影响，或者在影响可快速运算范围内的点缩在一起，从而使得整棵树大小极大的减小。
因此，可以使用虚树的题目一般有 特殊点 之类的设定，多测并限定 特殊点 的总量。
P2495 [SDOI2011] 消耗战
一道经典的虚树题。
如果要考虑虚树，我们需要先考虑原树上是如何 DP 的。
DP
设 \(f(u)\) 表示切断 \(u\) 子树中所有能源所需要的代价。
记 \(v\) 表示 \(u\) 的儿子，\(w\) 为 \(u\) 到其父亲的边权。
若 \(u\) 有能源：
\[f(u) = w
\]
直接切断 \(u\) 到父亲的桥梁。
若 \(u\) 无能源：
\[f(u) = \min\{w,\sum f(v)\}
\]
虚树
接下来考虑有哪些点可以省去。
观察状态转移方程，能源点肯定需要保留，能源点两两之间的 LCA 也需要保留。
即如图若加粗的点为能源点，则 5，2，1，都需要保留。
