CodeM美团点评编程大赛初赛B轮 黑白树【DFS深搜+暴力】

[编程题] 黑白树

时间限制:1秒

空间限制:32768K

一棵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变黑
输出描述:
一个数表示最少操作次数
输入例子:
4
1
2
1
1 2 2 1
输出例子:
3

题目链接:https://www.nowcoder.com/question/next?pid=5599304&qid=105269&tid=8919747

分析:DFS深搜+暴力写法,可以参考一下的啦!

其实就是一个DFS递归啊,

子树全变黑的最优解:sum1,

在最优解sum1下最多还能向上延伸的点数,sum2,

sum3是,子树下不被选择的点作为备选的点,最多还能向上延伸的点数!

下面给出AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N =166666;
 4 typedef long long ll;
 5 vector<ll> T[N];
 6 ll n,a[N];
 7 struct Tree
 8 {
 9     ll ans;
10     ll maxn;
11     ll Gmaxn;
12 };
13 inline ll read()
14 {
15     ll x=0,f=1;
16     char ch=getchar();
17     while(ch<'0'||ch>'9')
18     {
19         if(ch=='-')
20             f=-1;
21         ch=getchar();
22     }
23     while(ch>='0'&&ch<='9')
24     {
25         x=x*10+ch-'0';
26         ch=getchar();
27     }
28     return x*f;
29 }
30 inline void write(ll x)
31 {
32     if(x<0)
33     {
34         putchar('-');
35         x=-x;
36     }
37     if(x>9)
38     {
39         write(x/10);
40     }
41     putchar(x%10+'0');
42 }
43 Tree DFS(ll xx,ll yy)
44 {
45     Tree ret={0,0,0};
46     ll sum1=0,sum2=-1,sum3=-1;
47     for(ll i=0;i<T[xx].size();i++)
48     {
49         ll to=T[xx][i];
50         if(to==yy)
51             continue;
52         ret=DFS(to,xx);
53         sum1+=ret.ans;
54         sum2=max(ret.maxn,sum2);
55         sum3=max(ret.Gmaxn,sum3);
56     }
57     if(sum2<=-1)
58     {
59         sum2=max(a[xx],sum3);
60         sum1+=1;
61     }
62     sum3=max(sum3,a[xx]);
63     ret.ans=sum1;
64     ret.maxn=sum2-1;
65     ret.Gmaxn=sum3-1;
66     return ret;
67 }
68 int main()
69 {
70     ll p;
71     n=read();
72     for(ll i=1;i<=n-1;i++)
73     {
74         p=read();
75         T[p].push_back(i+1);
76     }
77     for(ll i=1;i<=n;i++)
78     {
79         a[i]=read();
80         a[i]--;
81     }
82     write(DFS(1,0).ans);
83     return 0;
84 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

27860
来自专栏文渊之博

小议如何使用APPLY

简介 如果你打算为在结果集中的每条记录写一个调用表值函数或者表值表达式的select语句,那么你就能用到APPLY 操作符来实现。一般又两种形式写法: 第一种格...

18850
来自专栏Golang语言社区

算法基础:最大递减数问题(Golang实现)

给出一个非负整数,找到这个非负整数中包括的最大递减数。一个数字的递减数是指相邻的数位从大到小排列的数字。 如: 95345323,递减数有:953,95,53,...

35150
来自专栏乐沙弥的世界

SQL, PL/SQL 之NUMBER数据类型

    NUMBER数据类型在Oracle中使用的较为广泛,可以存储零值,正负数,以及定长数,对于这个数据类型有个几个概念要搞清,否则容易搞混,下面给出具体描述...

10920
来自专栏章鱼的慢慢技术路

Direct3D 11 Tutorial 3: Shaders and Effect System_Direct3D 11 教程3:着色器和效果系统

在上一个教程中,我们设置了一个顶点缓冲区并将一个三角形传递给GPU。 现在,我们将逐步完成图形管道并查看每个阶段的工作原理。 将解释着色器和效果系统的概念。

10010
来自专栏智能算法

自动还原魔方算法数据结构

来自:CSDN博客 作者:寸辰 链接:http://blog.csdn.net/cun_chen/article/details/50261787(点击尾部阅读...

36050
来自专栏C语言及其他语言

【每日一题】1426: [蓝桥杯][历届试题]九宫重排

如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面...

13330
来自专栏数据结构与算法

P1418 选点问题

题目描述 给出n个点,m条边,每个点能控制与其相连的所有的边,要求选出一些点,使得这些点能控制所有的边,并且点数最少。同时,任意一条边不能被两个点控制 输入输出...

357110
来自专栏landv

c语言_头文件

23930
来自专栏java系列博客

UML——类图2

24150

扫码关注云+社区

领取腾讯云代金券