网络巡视2

成绩 100 开启时间 2020年06月17日 星期三 17:35
折扣 0.8 折扣时间 2020年06月17日 星期三 17:35
允许迟交 是 关闭时间 2020年06月17日 星期三 17:35
输入文件 Net2.in 输出文件 Net2.out

 

【题目描述】网络巡视2（Net2）HDU 1054

通信公司的网络各结点构成了一棵树，为了防止破坏，需要在一些结点安置巡视岗，安置巡视岗的结点不仅可以看到相邻结点的情况，还可以看到结点之间的道路情况。请问最少需要安置多少个岗位。

【输入格式】

输入包括多组数据，每组数据第一行一个整数n (0＜n≤1 500)表示树的结点数。随后n行依次描述各结点之间的关系。

【输出格式】

每组数据输出一个整数，即最少安置数。

【输入样例】

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

【样例说明】

第一组样例描述的树如图4.63所示。

图4.63