比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
小金 | AAAAAAAAAA | 0.125 s | 5.92 MiB | 100 |
┭┮﹏┭┮ | AAAAAAAAAA | 0.542 s | 34.43 MiB | 100 |
darkMoon | AAAAAAAAAA | 0.720 s | 34.20 MiB | 100 |
flyfree | AAAAAWWWWW | 0.134 s | 8.31 MiB | 50 |
袁书杰 | AAAWAEEEEE | 1.157 s | 5.21 MiB | 40 |
LikableP | AAATATTTTT | 12.078 s | 18.63 MiB | 40 |
wzh0425 | WAATTEEEEE | 5.117 s | 3.34 MiB | 20 |
AeeE5x | WWWWAWWWWW | 0.030 s | 3.38 MiB | 10 |
djyqjy | WWWWAWWWWW | 0.030 s | 3.60 MiB | 10 |
ht骨架 | WWWWWWWWWW | 0.030 s | 3.36 MiB | 0 |
Untitled | WWWTTEEEEE | 6.451 s | 3.39 MiB | 0 |
有一棵点数为$N$的树,树边有边权。给你一个在$0-N$之内的正整数$K$,你要在这棵树中选择$K$个点,将其染成黑色,并将其他的$N-K$个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。
第一行两个整数$N$,$K$。
接下来$N-1$行每行三个正整数$fr,to,dis$,表示该树中存在一条长度为$dis$的边$(fr,to)$。输入保证所有点之间是联通的。
输出一个正整数,表示收益的最大值。
3 1 1 2 1 1 3 2
3
5 2 1 2 3 1 5 1 2 3 1 2 4 2
17
在第二个样例中,将点$1$,$2$染黑就能获得最大收益。
对于$30$%的数据,$N<=20$
对于$50$%的数据,$N<=100$
对于$100$%的数据,$N<=2000,0<=K<=N$