重建道路
问题描述
5·12大地震后,给四川带来了毁灭性的打击。四川人们在全国各族人民的热心帮助下自力更生,重建家园。人们用N个牲口棚(1<=N<=150,编号1..N)重建了农夫老杨的牧场,由于人们没有时间建设多余的道路,所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此牧场运输系统可以被构建成一棵树。如今四川地区余震不断,老杨想要知道另一次地震会造成多严重的破坏,有些道路一旦被破坏,就会使一棵含有P(1<=P<=n)个牲口棚的子树和剩余的牲口相分离,老杨向知道这些道路的最小数目。
输入格式
第1行2个数,N和P。
第2..n行,每行2个整数i和j,表示结点i是结点j的父结点。
输出格式
单独一行,包含一旦被破坏将分离出恰含p个结点的子树的道路的最小数目。
输入样例
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
输出样例
2
样例说明
如果道路1-4和1-5被破坏,含有结点(1,2,3,6,7,8)的子树将被分离出来。
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 5
- 已通过
- 2
- 通过率
- 40%
- 上传者