树形动态规划⚓︎
例题：没有上司的舞会
该问题为打家劫舍III 的多叉树推广。
动态规划问题的表示：
- 状态表示：
- 集合：
- \(f(u,0)\) 表示所有从以 \(u\) 为根的子树中选择，但是不选 \(u\) 这个点的方案；
- \(f(u,1)\) 表示所有从以 \(u\) 为根的子树中选择，并且选择 \(u\) 这个点的方案；
- 属性：欢乐值的最大值。
- 集合：
- 状态计算：按照 \(f(u,0)\) (不选 \(u\)) 和 \(f(u,1)\) (选 \(u\)) 分类讨论。
可得：
\[
\begin{cases}
f\left( u,0 \right) =\sum_{s_i:\ \mathrm{son}\ \mathrm{of}\ u}{\max \left[ f\left( s_i,0 \right) ,f\left( s_i,1 \right) \right]}\\
f\left( u,1 \right) =\sum_{s_i:\ \mathrm{son}\ \mathrm{of}\ u}{f\left( s_i,0 \right)}\\
\end{cases}
\]