CF627D.Preorder Test

For his computer science class, Jacob builds a model tree with sticks and balls containing n nodes in the shape of a tree. Jacob has spent a__i minutes building the i-th ball in the tree.

Jacob's teacher will evaluate his model and grade Jacob based on the effort he has put in. However, she does not have enough time to search his whole tree to determine this; Jacob knows that she will examine the first k nodes in a DFS-order traversal of the tree. She will then assign Jacob a grade equal to the minimum a__i she finds among those k nodes.

Though Jacob does not have enough time to rebuild his model, he can choose the root node that his teacher starts from. Furthermore, he can rearrange the list of neighbors of each node in any order he likes. Help Jacob find the best grade he can get on this assignment.

A DFS-order traversal is an ordering of the nodes of a rooted tree, built by a recursive DFS-procedure initially called on the root of the tree. When called on a given node v, the procedure does the following:

1. Print v.
2. Traverse the list of neighbors of the node v in order and iteratively call DFS-procedure on each one. Do not call DFS-procedure on node u if you came to node v directly from u.

为了他的计算机科学课程，雅各布用木棍和小球搭建了一棵包含 $n$ 个节点的模型树。雅各布花费了 $a_i$ 分钟来制作树中的第 $i$ 个小球。

雅各布的老师将评估他的模型，并根据他所付出的努力给出成绩。然而，老师没有足够的时间遍历整棵树来确定这一努力程度；雅各布知道，老师只会检查该树在深度优先搜索（DFS）遍历顺序下的前 $k$ 个节点。随后，老师将给予雅各布的成绩等于这 $k$ 个节点中最小的 $a_i$ 值。

尽管雅各布没有足够的时间重建模型，但他可以选择老师 DFS 遍历时的起始根节点。此外，他还可以任意重新排列每个节点的邻接点列表顺序。请帮助雅各布找出他在此作业中所能获得的最高成绩。

DFS 遍历顺序是指对一棵有根树的节点所定义的一种顺序，它由一个从树根开始递归调用的 DFS 过程生成。当该过程被调用在某个节点 $v$ 上时，执行以下操作：

1. 输出 $v$；
2. 按顺序遍历节点 $v$ 的邻接点列表，并依次对每个邻接点递归调用 DFS 过程；但若节点 $u$ 是直接通向 $v$ 的父节点，则不对 $u$ 调用 DFS 过程。

The first line of the input contains two positive integers, n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ n) — the number of balls in Jacob's tree and the number of balls the teacher will inspect.

The second line contains n integers, a__i (1 ≤ a__i ≤ 1 000 000), the time Jacob used to build the i-th ball.

Each of the next n - 1 lines contains two integers u__i, v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) representing a connection in Jacob's tree between balls u__i and v__i.

输入的第一行包含两个正整数 $n$ 和 $k$（$2 \leq n \leq 200\,000$，$1 \leq k \leq n$）——分别表示雅各布的树中球的数量以及老师将要检查的球的数量。

第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 1\,000\,000$），表示雅各布构建第 $i$ 个球所用的时间。

接下来的 $n-1$ 行每行包含两个整数 $u_i$、$v_i$（$1 \leq u_i,\, v_i \leq n$，$u_i \neq v_i$），表示雅各布的树中球 $u_i$ 与球 $v_i$ 之间的一条连接。

Print a single integer — the maximum grade Jacob can get by picking the right root of the tree and rearranging the list of neighbors.

输出一个整数——雅各布通过选择合适的树根并重新排列邻居列表所能获得的最高分数。

In the first sample, Jacob can root the tree at node 2 and order 2's neighbors in the order 4, 1, 5 (all other nodes have at most two neighbors). The resulting preorder traversal is 2, 4, 1, 3, 5, and the minimum a__i of the first 3 nodes is 3.

In the second sample, it is clear that any preorder traversal will contain node 1 as either its first or second node, so Jacob cannot do better than a grade of 1.

在第一个样例中，Jacob 可以将树以节点 2 为根，并将其邻居按顺序 4、1、5 排列（其余所有节点的邻居数均不超过两个）。由此得到的先序遍历结果为 2、4、1、3、5，且前 3 个节点中最小的 $a_i$ 为 3。

在第二个样例中，显然任意先序遍历都将节点 1 作为第 1 个或第 2 个节点，因此 Jacob 无法获得优于 1 的得分。