[SOJ 1140]国王的遗产

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 legacy.in 输出文件 legacy.out

【问题描述】

哈丁国的国王一生善于管理,勤于政务,于是聚积了大量的财富。但他众多的孩子都不争气,相互间时常勾心斗角,却没有一个真正能接受国王传位的人。为了避免将来某儿子一人独揽大权,又出于不能让权力过度分散的考虑,临终前,国王决定将他一生的财富打造出了一条很大的金块链,这条金块链的形状比较特别,它由n块大块的黄金组成,国王准备了n-1条链条,将某些相邻的两块大黄金用链条连接起来,最后构成一条连通的金块链,如图5.8.1所示。

图5.8.1国王的遗产金块链示意图

国王对每块黄金编上号(1~n),然后立下了遗嘱:

(1)儿子们按照年龄大小顺序,在现存的金块链中获得遗产。

(2)对于某个儿子,他可以在现存金块链中剪掉某条链条,获得不超过现有金块总数一半的那一部分。

(3)某个儿子取得他那部分金块后,剩下的部分由他后面的弟弟们继续操作。

(4)最后一个儿子获得剩下的那些金块,国王将保证每个儿子都能获得遗产。

国王的儿子们都是贪婪的,他们都会选取使自己得到最多的金块的那条链条来剪,当然,有时选取的方案不是惟一的,但是儿子们都会选择使自己获得的“金块组编号”最小的那一条链来剪。“金块组编号”大小定义为:对于长度相同为L的两个有序数组A和B,A<b当且仅当存在一个整数i(0<i≤l),使得a[1]=b[1],···,a[i-1]=b[i-1]且a[i]<b[i]。


【输入】

输入格式(输入文件名legacy.in)

输入数据第1行为一个整数n(1≤n≤30000)和一个整数k(1≤k≤100),分别表示金块的总数与国王儿子的数量。接下来n-1行,每行两个整数x和y,表示编号为x的金块与编号为y的金块用链条连接起来。


【输出】

输出格式(输出文件名legacy.out)

输出数据只有一行,包含有k个整数,分别表示每个儿子获得金块的数量(由大儿子到最小的儿子)。


【输入输出样例】

输入(legacy.in)

6 3

1 2

2 3

3 4

2 5

3 6

输出(legacy.out)

3 1 2