题目描述

给定一棵 $n$ 个结点以 $1$ 为根的有根树，结点编号为 $1$ 到 $n$，每个结点 $i$ 关联一个非负整数 $a_i$，表示该结点的处理耗时。定义一条从根出发的路径合法当且仅当其满足以下条件：

• 必须遍历整棵树，且最终回到结点 $1$；
• 每条边最多经过 $2​$ 次；

设路径长度为 $L$，设结点 $i$ 第一次被访问的时间为 $r_i$，则定义其完成时间为：

• 若 $i \ne 1$，则 $t_i = r_i + a_i$；
• 若 $i = 1$，则 $t_1 = L + a_1$。

定义一条合法路径的耗时：

请对于所有合法路径，求出最短的耗时。

输入格式

第一行一个正整数 $n$ ($1 \le n \le 3 \times 10^5$)；

第二行 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)；

接下来 $n-1$ 行，每行两个正整数 $u_i, v_i$，表示树中的一条无向边。

输出格式

输出一个整数 $T$，表示所有合法路径中最短的耗时。

样例输入

5
1 4 1 3 9
1 2
2 3
2 4
1 5

样例输出

10

数据范围

对于 $40\%$ 的数据，$n \le 10$；

对于 $60\%$ 的数据，$n \le 3000$；

另有 $8\%$ 的数据满足 $\forall i \in [1, n-1], v_i = u_i + 1$；

另有 $8\%$ 的数据满足 $\forall i \in [1, n-1], u_i = 1, v_i = i + 1$。

对于 $100\%$ 的数据，$1 \le n \le 3 \times 10^5, 0 \le a_i \le 10^9$，且输入构成一棵树。