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 }
时间: 06-28

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

CodeM美团点评编程大赛初赛A轮

因为语文太差弃赛,第一个追及问题看不懂我就弃赛了.打进复赛确实挺难的,补一下题,锻炼下就行了. 身体训练 时间限制:1秒 空间限制:32768K 美团外卖的配送员用变速跑的方式进行身体训练.他们训练的方式是:n个人排成一列跑步,前后两人之间相隔 u 米,每个人正常速度均为 v 米/秒.当某个配送员排在最后的时候,他需要以当时自己的最高速度往前跑,直到超过排头的人 u 米,然后降回到原始速度 v 米/秒.每个人最初的最高速度为c[i] 米/秒,每轮衰减d[i] 米/秒,也就是说,如果i是第j个跑的

美团2017年CodeM大赛-初赛B轮 黑白树 (树形dp)

大意: 给定树, 初始每个点全为白色, 点$i$有权值$k_i$, 表示选择$i$后, 所有距离$i$小于$k_i$的祖先(包括i)会变为黑色, 求最少选多少个点能使所有点变为黑色. 链上情况的话, 直接从链头开始做一次线性dp就行了, 但是显然不能拓展到树上情况. 正解是从叶子往上贪心划分, 若当前点$x$为白色, 则从$x$子树内选择一个$y$, 满足$k[y]-dis(x,y)$最大, 这个显然可以用树形dp在O(n)时间求出. #include <iostream> #include

2014第六届华为编程大赛初赛第一轮

/*********************************************************************** 1.投票问题 输入若干候选人,以及投票,格式如下,输出(按输入候选人输入顺序)候选人以及得票,以及 无效票数. Input: addCandidate xx1 addCandidate xx2 addCandidate xx3 addCandidate xx4 addCandidate xx5 addCandidate xx6 vote xx2 vot

CodeM 2017美团点评编程大赛资格赛

音乐研究 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M 美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究.他有两段音频,每段音频是一个表示音高的序列.现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分. 具体地说,就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列,使得它们的 difference 最小.两段等长音频的 difference 定义为:difference = SUM(a[i] - b[i])2 (1 ≤ i ≤ n),

CodeM美团点评编程竞赛资格赛题

最近看到牛课网美团一个编程竞赛,想着做做看,结果一写就是两天..真是写不动了啊.话不多说,下面开始我的题解. 题目大致还是比较考察思维和代码能力(因为自己代码能力较弱,才会觉得比较考察代码能力吧= =!),难度由简到难变化也比较适中,有签到题.有算法实现,当然也有稍稍一点代码量的题.感谢美团点评,提供一套合适的题目~ 音乐研究 题目描述 美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究.他有两段音频,每段音频是一个表示音高的序列.现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分.具体地

【大坑特坑】第六届华为“创新杯”编程大赛初赛题目(第五场)

简直没法吐槽华为的服务器质量了,登一次半小时,提交一次等半小时,然后第二个题的结果还不知道呢,服务器就挂了... 题目本身倒是还挺简单的. A题是鸡兔同笼问题: 给出鸡和兔子的头数和脚数(可能不对),让你判断鸡的个数和兔子的个数..小学经典问题. 关键是不合法的情况,总共有4种. 1.头比脚多.. 2.脚是奇数= = 3.脚>4*头或者脚<2*头. so.出来了. #include <iostream> #include <cstring> #include <c

2014第六届华为编程大赛初赛第四轮

/*********************************************************************** 第一题 求n个整数的最大公约数 输入 第一行: n个整数 第二行:各个整数 以空格隔开 输出:公约数 例子: input: 4 10 15 20 25 output: 5 **********************************************************************/ #include <stdio.h>

【结果发布】第六届SeedCoder编程大赛初赛结果发布

微软俱乐部科技文化月seedcoder2014编程大赛已经初审完成. 评审小组选出最棒的作品进入决赛(现场答辩+陈述环节,由评委现场打分).终于排名由"初赛分数+现场答辩分"决定. 决赛答辩时间为:2014年4月20日(本周日)  晚上19:00     有讲座票派发 地点: 34号楼103教室 以下为初赛结果(依据队名排序): 算法组获奖的队伍名单 队伍 学院 年级 奖项 YOLO 计算机科学与project学院 大二 參加答辩 aaaaaa 软件学院 大三 參加答辩 mg 软件学院

BC 2015年百度之星程序设计大赛 - 初赛(1)(KPI-主席树)

KPI Accepts: 517 Submissions: 2185 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 你工作以后, KPI 就是你的全部了. 我开发了一个服务,取得了很大的知名度.数十亿的请求被推到一个大管道后同时服务从管头拉取请求.让我们来定义每个请求都有一个重要值.我的KPI是由当前管道内请求的重要值的中间值来计算.现在给你