도시 정비

알고리즘 나라에는 도시가 $N$개 있고, 도시를 잇는 고속도로가 $N-1$개 있다. 모든 도시는 고속도로를 따라 직접 또는 간접으로 이어져 있다.

알고리즘 나라는 도시를 하나 없애려고 한다. 도시가 없어지면 그 도시에 직접 연결된 고속도로도 함께 사라지고, 없어진 도시는 더 이상 정비하지 않는다.

도시를 정비하려면 정비 기기가 필요하다. 도시마다 필요한 정비 기기의 최소 가격이 정해져 있다. 어떤 도시의 최소 가격이 $x$이면 가격이 $x$ 이상인 기기로만 그 도시를 정비할 수 있다.

정비 기기는 고속도로로만 이동한다. 도시 정비는 급하지 않으므로, 남은 고속도로로 서로 이어져 있는 도시 집합 하나에는 정비 기기를 한 대만 쓴다.

당신은 정비 기기를 만드는 회사의 사장이다. 매출은 남은 도시를 모두 정비하는 데 드는 최소 비용이다. 도시를 하나 없앴을 때 나올 수 있는 가장 높은 매출을 출력하는 프로그램을 작성하여라.

첫째 줄에 양의 정수 $N$이 주어진다($2 \le N \le 10^6$). 도시에는 1번부터 $N$번까지 번호가 붙어 있다.

둘째 줄에는 1번 도시부터 $N$번 도시까지 필요한 정비 기기의 최소 가격이 순서대로 공백을 사이에 두고 주어진다. 모든 가격은 양의 정수이고, 가격의 합은 $2^{31}$보다 작다.

이어지는 $N-1$개의 줄에는 고속도로가 잇는 두 도시의 번호가 공백을 사이에 두고 주어진다.

첫째 줄에 도시를 하나 없앴을 때 가능한 가장 높은 매출을 출력한다.