| 题目名称 | 1962. [HAOI 2015]树上染色 |
|---|---|
| 输入输出 | haoi2015_t1.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-04-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 查看题解 | 分享题解 |
| 通过：148， 提交：318， 通过率：46.54% | ||||
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.018 s | 14.59 MiB | C++ |
 Asm.Def |
100 | 0.096 s | 66.33 MiB | C++ |
 BaDBoY |
100 | 0.109 s | 15.53 MiB | C++ |
 assassain |
100 | 0.121 s | 31.19 MiB | C++ |
 flyfree |
100 | 0.124 s | 8.32 MiB | C++ |
 蛤蛤 |
100 | 0.132 s | 31.21 MiB | C++ |
|
小金 |
100 | 0.135 s | 8.29 MiB | C++ |
 zzzzzfy |
100 | 0.138 s | 31.06 MiB | C++ |
|
HXF |
100 | 0.142 s | 31.22 MiB | C++ |
|
HXF |
100 | 0.145 s | 31.22 MiB | C++ |
| 本题关联比赛 | |||
| EYOI常规赛 2nd | |||
| EYOI常规赛 2nd | |||
| 2024暑假C班集训D | |||
| 关于 树上染色 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
代码里有详细注释，供DP做法理解
PS：这个N^3的正解DP不超时是很玄乎的//可能是开了O2( 补：题解已传，供大家参考理解。 | ||||
|
| ||||
|
| ||||
|
回复 @cstdio :
这是O(N^2)的,哥哥.....  Heaven
2017-08-09 19:38
7楼
| ||||
|
[b]
 [/u] xzz_233
2017-08-09 17:35
6楼
| ||||
|
感觉自己的代码看起来好舒服（雾
第一个树形dp（雾 | ||||
|
好慢，感觉像是降了一级复杂度Orz常数帝，绳命中第一道树形DP
 Satoshi
2015-05-15 19:26
4楼
| ||||
|
太弱了考场上连50分的dp都想不出……结果连暴力都没写打了个玄学的贪心……能骗到多少分呢？大概只能过一两个点吧……
顺便给题解打个广告：http://www.cnblogs.com/Asm-Definer/p/4466729.html | ||||
|
是的，你没有看错，正解就是那个O(N^3)的DP……
| ||||
Fmuckss
Chenyao2333
kZime
cstdio【题目描述】
有一棵点数为 $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$ 染黑就能获得最大收益。
【输入输出样例3】
【数据范围】
对于 $30\%$ 的数据，$N \leq 20$
对于 $50\%$ 的数据，$N \leq 100$
对于 $100\%$ 的数据，$N \leq 2000,0 \leq K \leq N$