树的分割

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 tree.in 输出文件 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