CF796C Bank Hacking

尽管 Inzane 成功找到了他心爱的骨头，但他的主人 Zane 还没有回来。为了寻找 Zane，他需要很多钱，而他却一分钱也没有。为了解决这个问题，他决定入侵银行。 有 $n$ 个银行，编号从 $1$ 到 $n$。还有 $n-1$ 条电线连接着这些银行。所有银行一开始都在线。每个银行也有一个初始强度：第 $i$ 个银行的初始强度为 $a_i$。 在继续之前，我们先定义一些关键词。如果存在一条电线直接连接银行 $i$ 和银行 $j$，则称它们为相邻银行。如果存在一个在线银行 $k$，使得银行 $i$ 和银行 $k$ 相邻，且银行 $k$ 和银行 $j$ 也相邻，则称银行 $i$ 和银行 $j$ 为半相邻银行。 当一个银行被攻破后，它将变为离线（不再在线），与其相邻或半相邻的其它银行的强度都将增加 $1$。 开始计划时，Inzane 会首先选择一个银行开始攻破。确实，被选中的银行的强度不得超过他电脑的强度。之后，他会不断选择下一个银行进行攻击，直到所有银行都被攻破。但每次可以继续攻破银行 $x$，只有在满足以下全部条件时才行： 1. 银行 $x$ 还在线，即尚未被攻破； 2. 银行 $x$ 与某个离线银行相邻； 3. 银行 $x$ 的强度不大于 Inzane 的电脑强度。 请你计算，为了最终能攻破所有银行，Inzane 至少需要多大强度的电脑？

第一行包含一个整数 $n$（$1\le n\le 3\cdot 10^{5}$），表示银行的数量。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$-10^9\le a_i\le 10^9$），表示每个银行的初始强度。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i, v_i \le n$，$u_i \ne v_i$），表示有一条电线直接连接银行 $u_i$ 和银行 $v_i$。 保证银行之间的电线连接方式使得 Inzane 能够使用合适强度的电脑总能攻破所有银行。

输出一个整数，即 Inzane 至少需要多大强度的电脑，才能完成目标。

在第一个样例中，Inzane 可以用强度为 $5$ 的电脑攻破所有银行。以下是流程： - 初始状态下，所有银行的强度为 $[1,2,3,4,5]$。 - 他攻破第 $5$ 个银行，剩余银行的强度为 $[1,2,4,5,-]$。 - 他攻破第 $4$ 个银行，剩余银行的强度为 $[1,3,5,-,-]$。 - 他攻破第 $3$ 个银行，剩余银行的强度为 $[2,4,-,-,-]$。 - 他攻破第 $2$ 个银行，剩余银行的强度为 $[3,-,-,-,-]$。 - 最后攻破第 $1$ 个银行，任务完成。 在第二个样例中，Inzane 可以依次攻破银行 $4$、$2$、$3$、$1$、$5$、$7$、$6$。这样，他只需用一台强度为 $93$ 的电脑即可攻破所有银行。 由 ChatGPT 5 翻译