【bzoj2314】士兵的放置

经典问题：树的最小支配集问题

此题还需要统计方案数。

设：状态表示以 x 为根的子树全被覆盖的最少点数。

f1[x] 表示 x 被自己支配（选 x 点）, 以 x 为根的子树全被覆盖的最少点数。

f2[x] 表示 x 被儿子支配（不选 x 点，至少选一个儿子节点）, 以 x 为根的子树全被覆盖的最少点数。

f3[x] 表示 x 只被父亲支配（不选 x 点，也不能选 x 点的儿子，x 的父亲必选）, 以 x 为根的子树全被覆盖的最少点数。

显然最后的答案为 min(f1[1],f2[1])

计算过程：

f1[x] = ∑ min(f1[son],f2[son],f3[son])

f3[x] = ∑ f2[son]

关键在于 f2[x]，要求儿子选择 f1[son] 与 f2[son] 中较小的那个，并且还应满足至少有一个儿子选择 f1[son]。

那么考虑，枚举到某一个儿子时，之前的儿子只有两种选择：存在选 f1 的、不存在选 f1 的。

对于存在，该儿子可能选 f1 或 f2；

对于不存在，该儿子只能选 f1。

方案统计利用加法、乘法原理统计即可。