← 返回题目列表

Codeforces · 627/D

D. 预购测试

中文机器翻译题面 查看原题

在计算机科学课上,Jacob 使用棍子和球构建了一个模型树,其中包含 n 个树形节点。雅各布花了 ai 分钟在树上建造了第 i 个球。

雅各布的老师将根据雅各布付出的努力来评估他的模型和评分。但是,她没有足够的时间搜索他的整棵树来确定这一点; Jacob 知道她将在树的 DFS 顺序遍历中检查前 k 个节点。然后,她将为 Jacob 分配一个等于她在这 k 个节点中找到的最小 ai 的等级。

虽然 Jacob 没有足够的时间来重建他的模型,但他可以选择他的老师开始的根节点。此外,他可以按照他喜欢的任何顺序重新排列每个节点的邻居列表。帮助雅各布找到他在这项作业中可以获得的最好成绩。

DFS 顺序遍历是对有根树的节点进行排序,由最初在树的根上调用的递归 DFS 过程构建。当在给定节点 v 上调用时,该过程执行以下操作:

1. 打印 v。
2. 按顺序遍历节点 v 的邻居列表,并对每个节点迭代调用 DFS 过程。如果直接从 u 到达节点 v,请勿在节点 u 上调用 DFS 过程。

输入

输入的第一行包含两个正整数 n 和 k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ n) - 雅各布树中的球数和老师将检查的球数。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 1 000 000),即 Jacob 建造第 i 个球所用的时间。

接下来的 n - 1 行中的每一行都包含两个整数 ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi),表示雅各布树中球 ui 和 vi 之间的连接。

输出

打印一个整数——雅各布通过选择树的正确根并重新排列邻居列表可以获得的最高等级。

示例

输入 #1

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

输出 #1

3

输入 #2

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

输出 #2

1

注意

在第一个示例中,Jacob 可以在节点 2 处将树作为根,并将 2 的邻居按 4、1、5 的顺序排列(所有其他节点最多有两个邻居)。得到的前序遍历为2,4,1,3,5,前3个节点的最小ai为3。

在第二个示例中,很明显,任何先序遍历都将包含节点 1 作为其第一个或第二个节点,因此 Jacob 不能做得比 1 更好。