Problem E: 韭菜国数据结构习题
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$2$ |
正确数量 |
$2$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
|
当前分类(单击移除)：
单击选择分类：
韭菜国的数据结构课，是和别处不同的：都是教室墙上一块大黑板，老师在讲台上热情洋溢，学生却坐在下面打瞌睡，偶尔有随堂练习便翻一翻辅导书把答案抄上去——这是当年的事，现在的随堂习题都是请别的学校的算法竞赛选手原创的，大部分的学生多是对学习没兴趣的，做不出来，只有平时主动认真学习的，才能在老师把题目布置下来后，不疾不地说出思路，把答案写出来。今天的随堂习题是：有一棵 $n$ 个节点带边权的无根树（回想一下：无根树是一个联通的无向图，且任意两节点之间只有一条路径），你需要选出树上的一些边，保证这些边中任意两条之间都隔着至少 $k$ 条边，你需要求出满足限制的边集的权重之和的最大值。
第一行两个正整数 $n$ 和 $k$，含义见题面。保证 $n \le 1000, k \le n$。 接下来 $n-1$ 行，每行三个整数 $u, v, w$，表示 $u, v$ 之间存在一条权重为 $w$ 的边，保证 $1\le u,v\le n, 1\le w\le 1000$。
输出一个整数，表示满足限制的边集权重之和的最大值。
5 1
5 1 3
3 5 1
2 1 2
4 5 2