问题 4640 --3.信息学家cici(Expert in Informatics cici)

4640: 3.信息学家cici(Expert in Informatics cici)

题目描述

  cici在信息学中知识渊博,研究精深。可总有疏忽大意的时候,这不,在NOI2003中的《草莓》一题不慎失手:'(。比赛之后cici认真总结教训,呵呵,还根据那道题目改编了一道题目:D。

【题目背景】(摘自NOI2003试题)
尽管不少人都吃过鲜美的草莓,却很少有人真正观察过野草莓的生长。它们从自己的枝上伸出一根根长长的触须,遇到合适的地方就会扎根发芽,长出一株新的草莓。所以,当你在森林中遇到一株草莓的时候,通常就意味着你会在它的周围找到一片草莓田。但这些草莓并非能够无忧无虑地生长,树林中穿梭的鸟儿和偶尔路过的鹿群都喜欢吃这种美味的浆果。不过,草莓最大的威胁却是来自那些贪吃的棕熊。他们不但可以吃掉整整一片草莓,而且还会粗鲁地把一片草莓田搞得乱七八糟。于是每当一块草莓田越长越大之后,森林中的精灵们就会把这片草莓田分成k块种到k个空地中去,以免被粗鲁的棕熊搞乱。她们希望每块空地上恰好放上一块用触须连接在一起的草莓田。不过,如果一块空地里的草莓太少,它们就会感到孤单,所以精灵们希望无论哪块空地含有草莓的总重量都不要太小。可是天真的精灵并不知道怎样来做这件事情,你可以帮助她们吗?
 
(注意你不需要解决上面所述题目背景)

【本题任务】(需要你来解决)
    还是NOI2003那片美味可爱的草莓地,有n个草莓,1-n编号。每两个草莓之间至多有一根藤相连。与其不同的是这里的草莓构成一个无环图(很多人    比赛的时候没有发现大多数数据都是树:-(()。任务也不是要将草莓尽量平均的分割,而是剪断最少的藤,使得恰好可以分割出一个含有p个草莓节点的子树。

输入

第一行:两个整数N P
第二行-第n行:每行两个整数Xi Yi表示Xi Yi草莓间有藤相连。

输出

仅一行最少的剪断藤的数目。

样例输入输出

输入#1 复制
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
输出#1 复制

提示

【数据规模】
20%的数据0<N<=11
所有数据0<N<=150 0<P<=N


【样例说明】
剪掉1-4 1-5的边,可以得到(1, 2, 3, 6, 7, 8)为节点的子树。






序号 标题 作者 发表时间 费用 订购数 操作