华为题库已更新至:华为实习&秋招真题题库，请移步。

题解：树形DP

定义$f[i][j]$为以$i$为结点的子树中，不放消防栓/放消防栓（$j=0/1$）的最小个数

如果在第$i$个结点放置消防栓，那么对于结点$i$的所有子节点，都可以放置/不放置消防栓

则有$f[i][1]=\sum_{}^{}min(f[u][0],f[u][1]) (u\in {i|u是i的子节点})$

如果在第$i$个结点不放置消防栓，那么对于结点$i$的所有子节点，都必须要放置消防栓