题目描述

题目译自 XXI Olimpiada Informatyczna — III etap Rajd

在字节村，$n$ 栋房屋通过 $n-1$ 条道路相连，任意两栋房屋间有唯一路径。房屋编号为 $1$ 到 $n$，村长 Bajtazar 住在 $1$ 号房屋。为让村民用上最新科技，一批包含 $n$ 台电脑的包裹送到了他家，每栋房屋需分得一台。村民们一致决定，一旦收到电脑，就联网开玩最新版《农场工艺》（FarmerCraft）！

Bajtazar 将包裹装上他的小货车，准备出发分送电脑。油量有限，他每条路最多往返两次。在每栋房屋，他放下电脑后立刻赶往下一站。村民收到电脑后立即安装《农场工艺》，各家所需时间（取决于信息化水平）已知。送完所有电脑，Bajtazar 返回 $1$ 号房屋，也开始安装游戏。每条路通行时间为 $1$ 分钟，卸货时间忽略不计。

请你帮 Bajtazar 规划送货顺序，让所有村民（包括他自己）能尽早开玩《农场工艺》，即所有人完成游戏安装的最早时刻。

输入格式

输入第一行包含一个整数 $n$ $(2 \leq n \leq 500000)$，表示字节村的房屋数量。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$ $(1 \leq c_i \leq 10^9)$，$c_i$ 表示 $i$ 号房屋安装游戏的时间（分钟）。

接下来的 $n-1$ 行描述道路，每行两个整数 $a, b$ $(1 \leq a < b \leq n)$，表示 $a$ 号和 $b$ 号房屋间有直接道路。

输出格式

输出一行，一个整数，表示所有人能开始游戏的最短时间（分钟）。

6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6

11

Bajtazar 应按顺序送货到 $3, 2, 4, 5, 6, 1$ 号房屋。游戏安装完成时间（按房屋编号）分别为：$11, 10, 10, 10, 8, 9$ 分钟，所有人可在 $11$ 分钟后开始游戏。

若按 $3, 4, 5, 6, 2, 1$ 送货，安装时间为 $11, 16, 10, 8, 6, 7$ 分钟，需 $16$ 分钟才能开始游戏。

数据范围与提示

对于 $40\%$ 的数据，$n \leq 7000$。