5973: 进阶7.5.2 战略游戏

鲍勃喜欢完战略游戏，但他有时候找不到够快的解决方案。

限制他必须保卫一座中世纪城市，城市的道路形成一棵树。

他必须把最小数量的士兵放在节点上，这样才可以观察到所有道路。

请帮鲍勃找到放置的最小士兵数。

例如下图所示的树，解决方案是放置1个士兵(放置在节点1处)。

输入多个测试用例。

对每个测试用例：

第一行包含节点数$n(0<n\le 1500)$

接下来的$n$行，每行的描述为“节点编号:(道路数) 节点编号1 节点编号2 $\cdots$” 或 “节点编号:(0)”

节点编号为0~n-1，每个节点连接的道路数不超过10条。每条道路在输入数据中都只出现一次

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

1
2

题解点我