| 题目名称 | 359. 树的分割 |
|---|---|
| 输入输出 | tree.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2009-07-13加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：6， 通过率：33.33% | ||||
 __stdcall |
100 | 0.000 s | 0.00 MiB | C++ |
|
__stdcall |
100 | 0.000 s | 0.00 MiB | C++ |
 月落九天 |
10 | 0.000 s | 0.00 MiB | C++ |
 Magic_Sheep |
10 | 0.000 s | 0.00 MiB | C++ |
|
Magic_Sheep |
0 | 5.691 s | 19.20 MiB | C++ |
|
Magic_Sheep |
0 | 5.953 s | 40.07 MiB | C++ |
| 本题关联比赛 | |||
| 20090714 | |||
| 关于 树的分割 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这数据都错了多少时间了。。。。。催促管理员修复数据。
| ||||
|
这题数据有错....
不要再做无谓的挣扎了..... Magic_Sheep
2016-11-08 11:18
1楼
| ||||
【题面描述】
有一棵树，每个结点有一个权值，边表示连接关系。去掉 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