首页 > [HAOI2015]树上染色
开通博客写题解
头像 Kur1su
发表于 2021-03-24 10:07:58
Description 有一棵点数为 的树，树边有边权。给你一个在 之内的正整数 ，你要在这棵树中选择 个点，将其染成黑色，并将其他的 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。 Solution , 考虑二维树形 令 表示以 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 CoolGuang!
发表于 2021-03-25 20:47:46
题目大意 题目思路 看到树上问题就来补了 没想到还真是个好题 开始状态定义，定义代表以为根的子树，选择了个黑点，所达到的最大收益。 显然不可以转移，因为不知道其他的点黑点和白点选择情况，这里就有后效性了 所以考虑去除后效性【即不能对后面的状态产生影响】 显然直接计算距离是不可取的，但是对于两两 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 shyyhs
发表于 2021-03-18 18:07:34
思路 转移什么按边计算都是套路...小菜鸡每次接触边界问题就死翘翘啦.这题的第二维必须枚举,或者你提前算的贡献,因为你一直在想要不要重复的问题,所以你第一维肯定正序,但是注意当你时,本来就已经更新过了,已经不是这个值了,现在你又更新一次,这里就存在重复了.对于其他也没什么好讲的...我竟然上课理解这 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 sunrise__sunrise
发表于 2021-03-18 20:44:50
Solution 题目需要我们求解收益的最大值，那么我们就要拆分每一条边都来考虑一下，因为给出的是一棵树，所以对于每条边他会被计算的次数就是在它下方有几个黑节点乘上它上方有几个黑节点，再加上它下方有几个白节点乘上它上方有几个白节点。这样我们通过枚举根节点它的子树会存在几个黑节点进行动态规划处理。 我 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 CCSU_Clearlove
发表于 2021-03-24 00:06:43
## [HAOI2015]树上染***r /> [题目链接](https://ac.nowcoder.com/acm/problem/19996) 题意： 给你一颗大小为$n$的树，然后将树上的$k$个点染成黑色， $n - k$个点染成白色。问黑色两两之间的距离，与白色两两之间的距离和 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 jzdx（hjh）
发表于 2021-03-19 21:12:04
题号 NC19996名称 [HAOI2015]树上染色来源 [HAOI2015]每日一题三期汇总贴~ 题目描述 有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并将其他的N-K个点染成白色。 将所有点染色后，你会获得黑点两两之间的距离加上 展开全文
去ta的博客 赞 (1) 回复(2) 收起
头像 Eihuvita.
发表于 2021-03-18 18:47:09
题意 给你一棵树有个节点 然后给树上的个点将其染成黑色 然后剩下的染成白色 然后求黑点之间两两之间的距离加上白点之间两两之间的距离 求这个的最大值 树形 我们在的时候不仅仅时增加黑点的价值 还要处理出白点的价值 对于每条路径的贡献$$ code #include<bits/stdc++.h& 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 cheese_case
发表于 2022-04-02 11:41:53
感觉是时候总结一下树形背包的题目了，虽然都是树形背包，但是不同题目细节却有着不小的区别，这里我由两道题来分析不同点（尤其是状态是否合法的考虑以及转移循环的范围限制，对于dp 范围的限制一直都算是一个细节考虑），一题是本题，还有一题是经典树上背包 ————选课 先上选课 https://www.luo 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 熠丶
发表于 2021-03-17 22:17:06
做法：树形dp 思路 设siz[i]为以u为根的子树大小（包括u），dp[i][j]为以u为根的子树有j个黑点的最大收益之后是对于下面代码的解释for(int i=min(k,siz[u]);i>=0;i--)对于该节点子树的黑点的枚举（逆序可以考虑一维01背包做法）for(int j=0;j 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”