Acwing 323. 战略游戏

参考题目：Acwing 323. 战略游戏

题意
给定一个树，要使每条边上至少选一个点，求最少需要选几个点。
算法：树形dp
时间复杂度：

O

(

n

)

O(n)

O(n) (每个点只会被搜一次）
f 数组含义：
f[i][1]：在 i 号点放人的所有方案中的最小花费。f[i][0]：在 i 号点不放人的所有方案中的最小花费。根据定义，答案为 min(f[root][1], f[root][0]) ，即根节点不放人和放人的所有方案中的最小值。
st 数组含义：
st[i] = true，

Acwing 323. 战略游戏最先出现在Python成神之路。