题意：给你一棵树，要求选中一些点，使得每条边至少一个端点被选中。
令 dp_{i, 01} 表示以 i 为根的子树，是否选中该节点的最少选中节点数。易得：
dp_{i, 01}
i
\begin{aligned} f_{i, 0} =& \sum f_{u, 1} (u \in child_i) \\ f_{i, 1} =& \sum \min(dp_{u, 0}, dp_{u, 1}) \end{aligned}
树形 dp 即可。
code
🏠 返回仓库
Deleting the wiki page "P2016" cannot be undone. Continue?