题目描述

有一棵有根的树，树上有 $N$ 个顶点，顶点 $1$ 是树根。对于每个 $i = 1, 2, \ldots, N-1$ ，连接顶点 $u_i$ 和顶点 $v_i$ 的 $i$ 条边。根以外的每个顶点上都写有一个正整数：对于每个 $i = 2, 3, \ldots, N$ ，写在顶点 $i$ 上的整数是 $A_i$ 。高桥和青木将使用这棵有根树和一颗棋子进行下面的对弈。

棋子从顶点 $1$ 开始。直到对局结束，他们会重复以下步骤。

1. 首先，青木选择一个非根顶点，并用 $0$ 替换写在该顶点上的整数。
2. 接下来，高桥将棋子移动到棋子所在顶点的（直接）子顶点。
3. 然后，如果棋子位于叶子上，对局结束。即使不是这样，高桥也可以选择立即结束对局。

对局结束时，高桥的分数将是当时写在棋子所在顶点上的整数。高桥希望自己的分数越大越好，而青木则希望分数越小越好。请打印当两位棋手按照各自的目的进行最佳下棋时，高桥得到的分数。

输入格式

第一行输入 $N$

接下来一行输入 $N-1$ 个数字，$A_2$ $\ldots$ $A_N$

接下来 $N-1$ 行，每行两个整数 $u_i$ $v_i$ 代表一条树边。

输出格式

输出一个整数代表答案

7
2 4 6 5 6 10
1 2
1 3
2 4
2 5
5 6
5 7

5

30
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25
13 15
14 22
17 24
12 3
4 3
5 8
26 15
3 2
2 9
4 25
4 13
2 10
28 15
6 4
2 5
19 9
2 7
2 14
23 30
17 2
7 16
21 13
13 23
13 20
1 2
6 18
27 6
21 29
11 8

70

样例 1 解释

以下是两位棋手都以最佳状态下棋时的可能棋局进程。

1. 棋子从顶点 $1$ 开始。
2. 青木将写在顶点 $7$ 上的整数从 $10$ 改为 $0$ 。
3. 高桥将棋子从顶点 $1$ 移到顶点 $2$ 。
4. 青木将写在顶点 $4$ 上的整数从 $6$ 改为 $0$ 。
5. 高桥将棋子从顶点 $2$ 移到顶点 $5$ 。
6. 高桥选择结束对局。

对局结束时，棋子位于顶点 $5$ 上，当时在顶点 $5$ 上写入了整数 $5$ ，因此高桥的得分为 $5$ 。

提示

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq u_i, v_i \leq N$
• 给定图形是一棵树。
• 输入值均为整数。