PID387 / 机房病毒
题目描述

背景 Background

我们机房中了病毒,因此几乎什么都无法正常进入。为了解决这个病毒,我们花了好几天。终于在大家的共同努力下,病毒不再猖狂了。

题目描述 Description

我们的机房的所有计算机组成了一棵树,这是由于病毒,计算机无法两两完全连通的结果。所以,每台计算机能够直接连通的是它的孩子计算机和父亲计算机。话说某天晚上,我们发现病毒绝迹了,但是我们无法确认是否真的消灭干净了。因此我们需要派一些同学牺牲上课时间看守住所有的电脑两个小时,以确认没有任何病毒痕迹才能放心。我们当然想少耽误同学们的学习时间。因此我们需要找出一种方案,使所需要的看守人员最少。直接连通的两台计算机只需要一个人即可看守住。

数据范围

对于 100% 的数据,保证n≤1500。

输入格式

输入文件中数据表示一棵树,描述如下:

  第一行 N,表示树中结点的数目。

  从第二行开始,每行描述每个结点信息,依次为:该结点标号i,k(后面有k条边与结点I相连),接下来k个数,分别是每条边的另一个结点标号r1,r2,...,rk。

  对于一个n(1 < n <= 1500)个结点的树,结点标号在0到n-1之间,在输入文件中每条边只出现一次。

输出格式

输出数据只有一行,表示至少需要耽误多少学生的学习时间。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论