首页
比赛
题库
课程
竞赛讨论区
登录
/
注册
去牛客
首页
>
黑白树
35条解析
开通博客写题解
sunrise__sunrise
发表于 2020-04-08 15:15:53
题目描述 一棵n个点的有根树,1号点为根,相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色,初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i,i必须是白色的,然后i到根的链上(包括节点i与根)所有与节点i距离小于k[
展开全文
精神病科黄主任
发表于 2020-04-07 14:30:29
思路:看到树的题,第一想法往往就是先考虑dfs这题我们可以知道,叶子节点是一定要染色的,因为他染色是一个从叶子节点往父亲节点更新的过程。那么我们应该考虑dfs应该要维护什么?首先我们肯定是贪心的策略去做,就是我选了叶子节点开始染色,那么染过色的地方就尽量不要去选,这应该是最优策略。但其实这样是有错误
展开全文
与人无语
发表于 2020-04-12 15:28:21
这是一个用树来提升难度的贪心题(蒟蒻理解首先当你来到一个新节点时有两种情况1、此节点能被已染色的子节点覆盖 这时只要更新理论最大覆盖范围2、此节点不能被已染色的子节点覆盖 选择那个提供最大覆盖范围的子节点染***r>菜鸡的其他理解全在代码里面了QAQ #include <bits/std
展开全文
rk_no
发表于 2020-04-07 12:50:25
题目: 一棵n个点的有根树,1号点为根,相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色,初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i,i必须是白色的,然后i到根的链上(包括节点i与根)所有与节点i距离小于k[i
展开全文
Kur1su
发表于 2020-04-08 20:16:38
Solution 太菜了,看了雨巨的题解才发自己读错题了 自闭了一天题目提到如果我们选择i点i点到根的链上(包括节点i与根)所有与节点i距离小于k[i]的点都会变黑那么我们就可以考虑从叶子开始取,因为取非叶子节点永远无法将叶子节点染黑这样显然就可以用dfs递归从叶子往根染黑其次,我们发现从叶子节点往
展开全文
WA_TLE
发表于 2020-04-08 15:02:10
此题解与官方题解大概相差不大,甚至代码都大同小异???但也是个人理解,望能帮到你。为了方便描述,我们先来考虑最简单的树,如图,每个节点最多只有一个子节点。对于这个图我们要怎么染色使得最少呢?由于每个节点只能由自己染色或由其子节点染色来影响它变成黑色,故显然叶子节点必然要染色。即给8染上黑色。现在我们
展开全文
shyyhs
发表于 2020-04-11 14:44:59
先给大家看看样例的图.思路:从最底下开始考虑,消耗了其价值肯定要走完,然后没消耗的就要保留到现在消耗1能造成的最大价值.下面的代码有注释.大家看看就懂了,不懂私聊~ #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio
展开全文
wxyww
发表于 2020-04-08 09:51:49
solution 比较容易想到的一个思路就是从深度更大的点开始选,每当遇到没有没变黑的点就选择它。 但是这样实际上是有问题的,选择当前没有被染色的点向上可以伸长的长度可能还不如选择其子树中的某个点更优。我们可以通过调整选择顺序,使得先选择这个更优的点。 所以我们每次更新K[u]为K[u]和所有K[v
展开全文
回归梦想
发表于 2020-04-09 17:38:10
试题链接 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format:%lld 题目描述 一棵n个点的有根树,1号点为根,相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色,初始的时候所有点
展开全文
cheese_case
发表于 2022-03-10 18:26:15
这题容易想到要从下向上贪心,因为从一个点开始只能染色其以及其上方的一些点,而其下方的点需要额外考虑染色,故而从叶子节点开始考虑染色,叶子节点必须染色 其范围是k[i],但是并不是最上面一个点才继续染色,而是当前染色点所包含所有点染色后这些点所能达到的最远距离,如果还需要染色,则染可以更新最远距离相对
展开全文
查看本题
查看本题讨论
相关比赛
7-美团2017年CodeM大赛-初赛B轮
进入比赛
28260-牛客竞赛动态规划专题班树型dp练习
进入比赛
29482-2022年大学生程序设计竞赛(A类)校内选拔赛
进入比赛
33736-QUST_Round_#1
进入比赛
35652-七中万达5月29日训练
进入比赛
等你来战
查看全部
2025牛客五一集训派对day4
报名截止时间:2025-05-04 17:00
2025牛客五一集训派对day5
报名截止时间:2025-05-05 17:00
牛客练习赛138
报名截止时间:2025-05-09 21:30
牛客周赛 Round 92
报名截止时间:2025-05-11 21:00
哈尔滨华德学院第十六届程序设计竞赛(同步赛)
报名截止时间:2025-05-13 20:30
牛客小白月赛116
报名截止时间:2025-05-16 21:00
牛客AI人机大战巅峰赛1
报名截止时间:2025-05-17 17:00
2025牛客暑期多校训练营1
报名截止时间:2025-07-15 17:00
扫描二维码,关注牛客
意见反馈
下载牛客APP,随时随地刷题