首页 > 试题广场 >

黑白树

[编程题]黑白树
  • 热度指数：148 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

输入描述:
第一行一个整数n (1 ≤ n ≤ 10^5)
接下来n-1行，每行一个整数，依次为2号点到n号点父亲的编号。
最后一行n个整数为k[i] (1 ≤ k[i] ≤ 10^5)

样例解释:
对节点3操作，导致节点2与节点3变黑
对节点4操作，导致节点4变黑
对节点1操作，导致节点1变黑


输出描述:
一个数表示最少操作次数
示例1

输入

4
1
2
1
1 2 2 1

输出

3
算法知识视频讲解
开通博客
头像 sunrise__sunrise
发表于 2020-04-08 15:15:53
题目描述 一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[ 展开全文
去ta的博客 赞 (10) 回复(2) 收起
头像 精神病科黄主任
发表于 2020-04-07 14:30:29
思路：看到树的题，第一想法往往就是先考虑dfs这题我们可以知道，叶子节点是一定要染色的，因为他染色是一个从叶子节点往父亲节点更新的过程。那么我们应该考虑dfs应该要维护什么？首先我们肯定是贪心的策略去做，就是我选了叶子节点开始染色，那么染过色的地方就尽量不要去选，这应该是最优策略。但其实这样是有错误 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 与人无语
发表于 2020-04-12 15:28:21
这是一个用树来提升难度的贪心题（蒟蒻理解首先当你来到一个新节点时有两种情况1、此节点能被已染色的子节点覆盖 这时只要更新理论最大覆盖范围2、此节点不能被已染色的子节点覆盖 选择那个提供最大覆盖范围的子节点染***r>菜鸡的其他理解全在代码里面了QAQ #include <bits/std 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 rk_no
发表于 2020-04-07 12:50:25
题目： 一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Kur1su
发表于 2020-04-08 20:16:38
Solution 太菜了,看了雨巨的题解才发自己读错题了 自闭了一天题目提到如果我们选择i点i点到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑那么我们就可以考虑从叶子开始取,因为取非叶子节点永远无法将叶子节点染黑这样显然就可以用dfs递归从叶子往根染黑其次,我们发现从叶子节点往 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 WA_TLE
发表于 2020-04-08 15:02:10
此题解与官方题解大概相差不大，甚至代码都大同小异？？？但也是个人理解，望能帮到你。为了方便描述，我们先来考虑最简单的树，如图，每个节点最多只有一个子节点。对于这个图我们要怎么染色使得最少呢？由于每个节点只能由自己染色或由其子节点染色来影响它变成黑色，故显然叶子节点必然要染色。即给8染上黑色。现在我们 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 shyyhs
发表于 2020-04-11 14:44:59
先给大家看看样例的图.思路:从最底下开始考虑,消耗了其价值肯定要走完,然后没消耗的就要保留到现在消耗1能造成的最大价值.下面的代码有注释.大家看看就懂了,不懂私聊~ #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 wxyww
发表于 2020-04-08 09:51:49
solution 比较容易想到的一个思路就是从深度更大的点开始选，每当遇到没有没变黑的点就选择它。 但是这样实际上是有问题的，选择当前没有被染色的点向上可以伸长的长度可能还不如选择其子树中的某个点更优。我们可以通过调整选择顺序，使得先选择这个更优的点。 所以我们每次更新K[u]为K[u]和所有K[v 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 回归梦想
发表于 2020-04-09 17:38:10
试题链接 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format:%lld 题目描述 一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 cheese_case
发表于 2022-03-10 18:26:15
这题容易想到要从下向上贪心，因为从一个点开始只能染色其以及其上方的一些点，而其下方的点需要额外考虑染色，故而从叶子节点开始考虑染色，叶子节点必须染色 其范围是k[i],但是并不是最上面一个点才继续染色，而是当前染色点所包含所有点染色后这些点所能达到的最远距离，如果还需要染色，则染可以更新最远距离相对 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 美团 动态规划 测试开发工程师 树形dp 大数据开发工程师 树 Java工程师
来自：CodeM 2017美...
难度：
2条回答 4702浏览

热门推荐

通过挑战的用户

相关试题

黑白树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号