Bob 喜欢玩电脑游戏特别是战略游戲。但是他经常无法找到快速玩过游戏的方法现在他有个问题。
现在他有座古城堡古城堡的路形成一棵树。他要在这棵树的节点上放置最少数目的士兵使得这些士兵能够瞭望到所有的路。
注意:某个士兵在一个节点上时与该节点相连的所有边都将能被瞭望到。
请你編一个程序给定一棵树,帮 Bob 计算出他最少要放置的士兵数
输入数据表示一棵树,描述如下
第一行一个数 N ,表示树中节点的数目
第②到第 N+1 行,每行描述每个节点信息依次为该节点编号 i,数值 kk表示后面有 k条边与节点 i相连,接下来 k个数分别是每条边的所连节点编号 r1,r2,?,rk。
对于一个有 N个节点的树节点标号在 0到 N-1之间,且在输入文件中每条边仅出现一次
输出仅包含一个数,为所求的最少士兵数
如果子樹的根节点不放士兵,那么根节点的子节点就必须全放士兵