树的分割

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file tree.in Output file tree.out

有一棵树,每个结点有一个权值,边表示连接关系。去掉 k-1 条边,就可以把这棵树分成 k 棵树。求如何分割使得你的分割方案中权和最小的那棵树的权和最大。

输入文件: tree.in

第一行为两个整数 n k 。 n 表示结点总数, k 为分割的数目。 (0<k<=n<=500)

第二行为 n 个整数,依次表示每个 结点 的权值( 1 到 1000 之间的整数)。

接下来的 n-1 行每行两个整数 p q ,表示第 p 个结点 和第 q 个结点 相连接(保证是树状结构)。

输出文件: tree.out

一个整数,表示你的分割方案中使得权和最小的那部分权和尽量大的值。

 

【样例输入】 tree.in

3 2
15 10 4
1 2
2 3
 

【样例输出】 tree.out

14