2. 树的分割

【题面描述】

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

【输入格式】

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

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

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

【输出格式】

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

【样例输入】

3 2
15 10 4
1 2
2 3

【样例输出】

14