FarmCraft

바이트빌 마을에는 집이 $n$채 있고, 길 $n-1$개가 그 집들을 잇는다. 어느 두 집 사이에도 오가는 경로가 정확히 하나뿐이다. 집에는 $1$번부터 $n$번까지 번호가 붙어 있으며, $1$번 집에는 마을을 관리하는 바이트아사르가 산다.

농촌 정보화 사업으로 컴퓨터 $n$대가 바이트아사르의 집에 도착했다. 집마다 컴퓨터를 한 대씩 놓아야 하고, 나눠 주는 일은 바이트아사르가 맡았다. 마을 사람들은 컴퓨터를 받는 대로 최신판 FarmCraft를 다 같이 시작하기로 이미 약속해 두었다.

바이트아사르는 컴퓨터를 모두 트럭에 싣고 길을 나선다. 연료는 각각의 길을 정확히 두 번씩 지날 만큼만 있다. 어떤 집에 닿으면 컴퓨터 한 대를 내려놓고 곧바로 다시 출발한다. 컴퓨터를 받은 집은 그 자리에서 FarmCraft를 설치하기 시작한다. 설치 시간은 집마다 다르고, 그 값은 미리 알려져 있다. 배달을 모두 마친 바이트아사르는 자기 집으로 돌아온 뒤에야 자기 컴퓨터에 게임을 설치한다. 길 하나를 지나는 데 $1$분이 걸리고, 컴퓨터를 내리는 시간은 $0$으로 본다.

바이트아사르를 포함한 마을 사람 전부가 게임을 함께 시작할 수 있는 가장 이른 시각을 구하라. 다시 말해 마지막 설치가 끝나는 시각이 가장 이르도록 배달 순서를 정했을 때, 그 시각을 구하면 된다.

첫째 줄에 바이트빌의 집 수 $n$이 주어진다. ($2 \le n \le 500\,000$)

둘째 줄에 정수 $c_1, c_2, \dots, c_n$이 공백 하나로 구분되어 주어진다. $c_i$는 $i$번 집에서 설치에 걸리는 시간이고, 단위는 분이다. ($1 \le c_i \le 10^9$)

이어지는 $n-1$개 줄에는 길이 한 줄에 하나씩 주어진다. 각 줄에는 정수 $a$와 $b$가 공백 하나로 구분되어 주어지며 ($1 \le a < b \le n$), $a$번 집과 $b$번 집이 길로 바로 이어져 있다는 뜻이다.

바이트아사르를 포함한 모든 집에서 설치가 끝나는 가장 이른 시각을 분 단위 정수 하나로 첫째 줄에 출력한다.

아래 그림은 예제에 주어진 마을이다.

바이트아사르가 $3, 2, 4, 5, 6$번 순서로 컴퓨터를 배달하고 집으로 돌아오면, $1$번 집부터 $6$번 집까지 설치가 각각 $11, 10, 10, 10, 8, 9$분에 끝난다. 그래서 $11$분이 지나면 다 같이 게임을 시작한다.

$3, 4, 5, 6, 2$번 순서로 배달하면 설치가 각각 $11, 16, 10, 8, 6, 7$분에 끝나므로, $16$분이 지나야 다 같이 시작할 수 있다.