#2942. 和平的国度

和平的国度

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

经过 100100 年的努力,CC 国终于出现了短暂的和平。但这种和平是暂时的,因为 CC 国仍然是军阀割据的局面。

CC国一共有 nn 个城市,有 n1n-1 个长度不一的虫洞将它们联系起来。每个军阀都控制着一个城市。

首都是 11 号城市。

两座城市的距离定义为,从一座城市穿越到另一座城市所经过的虫洞长度之和。

为了提高信息传输的效率,军阀们决定合并。

每次,他们可以选择与其有虫洞相接的两个城市结盟,并且每个联盟不能拥有超过 kk 个军阀。

一座城市只能结一个盟。

结盟后,信息在联盟内传递将不用花任何时间,在联盟间传递所需的时间为经过虫洞的长度。

试求出信息从首都传到每个城市的最小时间之和。

请注意,方案可能独立,不要求在同一种方案内。

输入格式

第一行两个正整数 n,kn,k

接下来 n1n-1 行,每行三个正整数 u,v,wu,v,w,表示 u,vu,v 两座城市有长度为 ww 的虫洞连接。

输出格式

输出一行一个整数,表示信息从首都传到所有城市的最小时间之和。

样例输入 1

11 3
1 2 1
1 3 3
3 4 4
3 5 2
4 6 7
6 7 6
6 8 2
5 9 8
2 10 3
2 11 2

样例输出 1

13

样例解释

这是样例的图。显然 1,2,3,4,5,10,111,2,3,4,5,10,11 都不需要时间,直接与 11 结盟就可以做到 00 时间内传达。

66 为例,它可以结盟成为 6,4,36,4,3,这样信息传输只会通过 131→3 的边,时间为 33,可以证明这是最优方案。

6,7,8,96,7,8,9 四个点最小用时分别为 3,4,4,23,4,4,2,总时间为 1313

数据范围 下表数据表示最大值。

Subtask n k 特殊性质 分值
1 10510^5 10 10
2 1
3 10410^4 保证数据是一条链 20
4 10510^5 60

对于100%100\% 的数据,1kn105,1w1091≤k≤n≤10^5,1≤w≤10^9

第二届小云雀杯提高组

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-4-23 19:30
结束于
2023-4-23 22:18
持续时间
2.8 小时
主持人
参赛人数
210