比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|
有一棵树,每个结点有一个权值,边表示连接关系。去掉 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