CF627D Preorder Test

Jacob 为他的计算机科学课程搭建了一个由木棒和小球组成的模型树，该树包含 $n$ 个节点，形状为一棵树。Jacob 为树上的第 $i$ 个小球花费了 $a_{i}$ 分钟。 Jacob 的老师会对他的模型进行评估并根据他的努力程度给Jacob打分。然而，老师没有足够的时间检查整棵树；Jacob 知道老师将按照 DFS 顺序遍历树的前 $k$ 个节点进行检查。然后，老师会根据这 $k$ 个节点中最小的 $a_{i}$ 给Jacob打分。 虽然Jacob没有足够的时间重建模型，但他可以选择老师从哪个节点（即树根）开始检查。此外，他还可以重新排列每个节点的邻居顺序。请帮助Jacob，求他能得到的最高分数。 DFS序遍历是指对有根树进行递归DFS操作第一次访问各节点的顺序。对于某个节点 $v$ ，其DFS操作如下： 1. 输出 $v$。 2. 按指定顺序遍历 $v$ 的邻居列表，对于每个邻居递归进行DFS（若某邻居是刚刚来自的节点，则不递归调用）。

第一行包含两个正整数 $n$ 和 $k$（$2 \leq n \leq 200000$，$1 \leq k \leq n$）——Jacob树中的小球数量，以及老师将检查的小球个数。 第二行包含 $n$ 个整数 $a_{i}$（$1 \leq a_{i} \leq 1000000$），表示Jacob制造第 $i$ 个小球所用的时间。 接下来的 $n-1$ 行每行包含两个整数 $u_{i}$, $v_{i}$（$1 \leq u_{i}, v_{i} \leq n$，$u_{i} \neq v_{i}$），表示Jacob树中小球 $u_{i}$ 与 $v_{i}$ 之间有一条连接。

输出一个整数，表示Jacob通过选择适当的根节点和邻居顺序能获得的最高分数。

在第一个样例中，Jacob 可以将树的根节点设为 $2$，并将 $2$ 的邻居顺序排列为 $4$、$1$、$5$（其他节点的邻居数不超过两个）。这样DFS前序遍历为 $2$、$4$、$1$、$3$、$5$，前 $3$ 个节点中 $a_{i}$ 的最小值为 $3$。 在第二个样例中，无论采用哪种前序遍历方式，第一个或第二个节点必定包含节点 $1$，所以Jacob无法获得比 $1$ 更高的分数。 由 ChatGPT 5 翻译