比赛场次 623
比赛名称 2024暑假C班集训D
比赛状态 已结束比赛成绩
开始时间 2024-07-13 08:00:00
结束时间 2024-07-13 12:00:00
开放分组 全部用户
注释介绍 dp专场,题目难度自行判断
题目名称 树上染色
输入输出 haoi2015_t1.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar小金 AAAAAAAAAA 0.125 s 5.92 MiB 100
Gravatar┭┮﹏┭┮ AAAAAAAAAA 0.542 s 34.43 MiB 100
GravatardarkMoon AAAAAAAAAA 0.720 s 34.20 MiB 100
Gravatarflyfree AAAAAWWWWW 0.134 s 8.31 MiB 50
Gravatar袁书杰 AAAWAEEEEE 1.157 s 5.21 MiB 40
GravatarLikableP AAATATTTTT 12.078 s 18.63 MiB 40
Gravatarwzh0425 WAATTEEEEE 5.117 s 3.34 MiB 20
GravatarAeeE5x WWWWAWWWWW 0.030 s 3.38 MiB 10
Gravatardjyqjy WWWWAWWWWW 0.030 s 3.60 MiB 10
Gravatarht骨架 WWWWWWWWWW 0.030 s 3.36 MiB 0
GravatarUntitled WWWTTEEEEE 6.451 s 3.39 MiB 0

树上染色

★★☆   输入文件:haoi2015_t1.in   输出文件:haoi2015_t1.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

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

【输入格式】

第一行两个整数$N$,$K$。

接下来$N-1$行每行三个正整数$fr,to,dis$,表示该树中存在一条长度为$dis$的边$(fr,to)$。输入保证所有点之间是联通的。

【输出格式】

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

【输入样例1】

3 1
1 2 1
1 3 2

【输出样例1】

3

【输入样例2】

5 2
1 2 3
1 5 1
2 3 1
2 4 2

【输出样例2】

17

【样例解释】

在第二个样例中,将点$1$,$2$染黑就能获得最大收益。

【数据范围】

对于$30$%的数据,$N<=20$

对于$50$%的数据,$N<=100$

对于$100$%的数据,$N<=2000,0<=K<=N$

大样例