题目描述
背景 Background
我们机房中了病毒,因此几乎什么都无法正常进入。为了解决这个病毒,我们花了好几天。终于在大家的共同努力下,病毒不再猖狂了。
题目描述 Description
我们的机房的所有计算机组成了一棵树,这是由于病毒,计算机无法两两完全连通的结果。所以,每台计算机能够直接连通的是它的孩子计算机和父亲计算机。话说某天晚上,我们发现病毒绝迹了,但是我们无法确认是否真的消灭干净了。因此我们需要派一些同学牺牲上课时间看守住所有的电脑两个小时,以确认没有任何病毒痕迹才能放心。我们当然想少耽误同学们的学习时间。因此我们需要找出一种方案,使所需要的看守人员最少。直接连通的两台计算机只需要一个人即可看守住。
数据范围
对于 100% 的数据,保证n≤1500。
输入格式
输入文件中数据表示一棵树,描述如下:
第一行 N,表示树中结点的数目。
从第二行开始,每行描述每个结点信息,依次为:该结点标号i,k(后面有k条边与结点I相连),接下来k个数,分别是每条边的另一个结点标号r1,r2,...,rk。
对于一个n(1 < n <= 1500)个结点的树,结点标号在0到n-1之间,在输入文件中每条边只出现一次。
输出格式
输出数据只有一行,表示至少需要耽误多少学生的学习时间。
样例输入
样例输出