/ CWOI / 题库 /

2017.07.05 P3 鸡的淘汰

2017.07.05 P3 鸡的淘汰

题目描述

王老师正在玩一款淘汰游戏,他所在学校有N个教室,这N个教室和教室之间的道路正好构成一颗树,现在他需要在教室上放置鸡来淘汰连接该教室的道路,你的任务是帮助他找到用最少的方式鸡淘汰所有道路的方案。
例如下图就只需要一个鸡放在 1 号节点。

输入格式

输入文件中有多组数据,每组数据的第一行 N 表示点的个数。接下来 N 行每行格式如下:
x:(k) a1 a2 … ak(x 为点的编号,k 为与其相连的子节点个数,a1, a2, …, ak 分别为子节点的编号)

输出格式

对于每组数据输出一行一个数,即最少鸡数。

样例输入

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

数据范围

对于 30%的数据,1 <= N <= 20
对于 60%的数据,1 <= N <= 200
对于 100%的数据,1 <= N<= 1500, 0 <= x < N

限制

1s

来源

CWOI新高二专题测试四

信息

难度
3
分类
动态规划 | 树形DP 点击显示
标签
递交数
15
已通过
7
通过率
47%
上传者