因为题目求的是覆盖树上所有点的所放置最少的消防站数量，因此此题需使用树形 DP 解决

状态转移方程

• dp[x][0] = 1dp[y][4] （ 为 的孩子 ）

要覆盖到爷爷的话必须选 ，并贪心地选 的第五种状态

• dp[x][1] = min ( dp[y][0] +dp[k][3] )（ 和 皆为 的孩子且)

的儿子中有一个一定覆盖的爷爷，同时覆盖到兄弟（因为 一定是选了），其他的儿子只需要覆盖的自己的儿子即可

• dp[x][2] = min ( dp[y][1] +dp[k][2] )（ 和 皆为 的孩子且)

有一个儿子覆盖到父亲，但无法覆盖到 的兄弟，所以其他儿子要覆盖到自己

• dp[x][3] =dp[y][2] （ 为 的孩子 ）

让每个儿子覆盖到自己

• dp[x][4] =dp[y][3] （ 为 的孩子 ）

让每个儿子覆盖到自己的儿子

遍历顺序

由叶子节点到根

边界条件

• 叶子节点

dp[x][0] = dp[x][1] = dp[x][2] =1 ;
dp[x][3] = dp[x][4] = 0 ;

• 非叶子节点

dp[x][0] = 1 , dp[x][1] = dp[x][2] = ;
dp[x][3] = dp[x][4] = 0 ;

输出答案

dp[1][2]（根包含自己和所有子树的最小答案）

评估效率

时间复杂度： 空间复杂度：