题目描述

消防员需要在城市中铺设消防栓。城市的道路可以看作是一棵连通且无回路的树，每个节点代表一个底座，边代表道路。

1.消防栓必须安装在底座上 => 消防栓只能放置在树的节点上

2.每条道路必须有消防栓盖 => 任何一条边都需要满足：所连接的两个节点至少有一个节点上有消防栓。

3.交叉路口只有一个消防栓底座，可以覆盖所有连接的道路 =》 每个节点最多放置一个消防栓，放置了就可以覆盖所有其他节点。

题目内容

消防员正在给城市铺设消防栓，城市的道路可以看作一个连通且无回路的图，每条道路有两个底座，消防栓必须铺设在底座上，每条道路必须有消防栓盖；交叉路口只有一个消防栓底座；交叉路口的消防栓可以覆盖连接的所有道路，求至少需要多少个消防栓才能覆盖城市所有的道路?

输入描述

每个 $case$ ，第一行一个整数 $n$ ，表示底座数。($1<=n<=1500$)

接下来 $n$ 行，每行以 $a:(b)$ 这样的格式开头，$a$ 表示底座的编号($0<=a<=n-1$), $b$ 表示与该底座相连接的底座数，接下来 $b$ 个数，表示与该底座相连的底座编号。

输出描述

一个数字，为需要的消防栓的最少个数

样例1

输入

3
0:(2) 1 2
1:(0)
2:(0)

输出

1

说明

$0$ 号底座与 $1$ 号和 $2$ 号相连，那么只需要在 $0$ 号铺设一个消防栓即可覆盖所有的道路，如下图所示：

样例2

输入

8
0:(3) 1 2 3
1:(1) 6
2:(0)
3:(0)
6:(1) 7
7:(2) 4 5
4:(0)
5:(0)

输出

3

说明

如图所示，在绿色节点上铺设消防栓即可覆盖全部道路

提示

动态规划

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写