P83276

树上染色

难度 7 级 初三 动态规划入门 树形
讨论 统计 4通过 13提交 30.8%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有一棵点数为 n 的树,树边有边权。给你一个在 0 \sim n 之内的正整数 k ,你要在这棵树中选择 k 个点,将其染成黑色,并将其他的 n-k 个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。

输入

第一行包含两个整数 n,k。

第二到 n 行每行三个正整数 u, v, w,表示该树中存在一条长度为 w 的边 (u, v)。输入保证所有点之间是联通的。

输出

输出一个正整数,表示收益的最大值。

样例

样例 1
输入
3 1
1 2 1
1 3 2
输出
3

提示

对于 100\% 的数据,0 \leq n,k,w \leq 2000。

来源

河南省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交