OI题库

【问题描述】

哈丁国的国王一生善于管理，勤于政务，于是聚积了大量的财富。但他众多的孩子都不争气，相互间时常勾心斗角，却没有一个真正能接受国王传位的人。为了避免将来某儿子一人独揽大权，又出于不能让权力过度分散的考虑，临终前，国王决定将他一生的财富打造出了一条很大的金块链，这条金块链的形状比较特别，它由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