比赛场次 37
比赛名称 20090714
比赛状态 已结束比赛成绩
开始时间 2009-07-14 08:10:00
结束时间 2009-07-14 11:50:00
开放分组 全部用户
注释介绍 2009暑期培训A班模拟测试
题目名称 树的分割
输入输出 tree.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分

树的分割

★★   输入文件:tree.in   输出文件:tree.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题面描述】

有一棵树,每个结点有一个权值,边表示连接关系。去掉 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