首页 > 试题广场 >

小美的美丽树

[编程题]小美的美丽树
  • 热度指数：1105 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小美在观察一棵美丽的无根树。

小团问小美：“小美，我考考你，如果我选一个点为根，你能不能找出子树大小不超过K的前提下，子树内最大值和最小值差最大的子树的根是哪个点？多个点的话你给我编号最小的那个点就行了。”

小美思索一番，说这个问题难不倒他。


输入描述:
第一行两个正整数N和K，表示全树有N个节点，要求子树大小不超过K。
第二行是N个正整数空格分隔，表示每个点的点权。以点编号从1到N的顺序给出点权。
接下来N-1行每行两个正整数表示哪两个点之间有边相连。
最后一行一个正整数root表示小团所选的根节点编号为root。


输出描述:
一行，一个正整数，含义如问题描述，输出在子树大小不超过K的前提下，子树内最大值和最小值差最大的子树的根的编号
示例1

输入

5 2
1 3 2 4 5
1 2
2 3
3 4
4 5
3

输出

2

备注:
对于30%的数据点有
对于100%的数据点有
各点上的权值有，对于K有
算法知识视频讲解
开通博客
头像 bytedancers
发表于 2021-03-13 02:01:01
DFS即可 from collections import defaultdict N, K = map(int, input().strip().split()) tree = list(map(int, input().strip().split())) adj = defaultdict(l 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
11条回答 4112浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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