AT_abc246_g [ABC246G] Game on Tree 3

有一棵包含 $N$ 个顶点的有根树，根为顶点 $1$。对于 $i = 1, 2, \ldots, N-1$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。此外，除了根以外的每个顶点上都写有一个正整数，具体来说，对于 $i = 2, 3, \ldots, N$，顶点 $i$ 上写有正整数 $A_i$。 高桥君和青木君将用这棵有根树和一个棋子进行如下对抗游戏： 初始时，棋子放在顶点 $1$。之后，重复以下步骤直到游戏结束： 1. 首先，青木君任选一个根以外的顶点，并将该顶点上写的整数改为 $0$。 2. 接着，高桥君可以将棋子移动到当前棋子所在顶点的任意一个直接子节点。 3. 然后，如果棋子位于叶子节点，游戏结束。即使不是叶子节点，高桥君也可以选择立即结束游戏。 游戏结束时，棋子所在顶点上当前写的整数即为高桥君的得分。高桥君希望最大化自己的得分，青木君则希望最小化高桥君的得分。请输出在双方都采取最优策略时高桥君的得分。

输入以如下格式从标准输入读入： > $N$ > $A_2\ A_3\ \ldots\ A_N$ > $u_1\ v_1$ > $u_2\ v_2$ > $\vdots$ > $u_{N-1}\ v_{N-1}$

输出答案。

### 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq A_i \leq 10^9$ - $1 \leq u_i, v_i \leq N$ - 给定的图是一棵树。 - 所有输入均为整数。 ### 样例解释 1 当双方都采取最优策略时，游戏可能的进行过程如下： 1. 初始时，棋子在顶点 $1$。 2. 青木君将顶点 $7$ 上的整数从 $10$ 改为 $0$。 3. 高桥君将棋子从顶点 $1$ 移动到顶点 $2$。 4. 青木君将顶点 $4$ 上的整数从 $6$ 改为 $0$。 5. 高桥君将棋子从顶点 $2$ 移动到顶点 $5$。 6. 高桥君选择结束游戏。 此时，棋子在顶点 $5$，顶点 $5$ 上的整数为 $5$，所以高桥君的得分为 $5$。 由 ChatGPT 4.1 翻译