15491번 - 도시 정비

알고리즘 나라는 N개의 도시로 구성되어 있다. 모든 도시들은 고속도로를 통해 직간접적으로 연결되어 있다. 고속도로는 N-1개만 존재한다.

알고리즘 나라는 도시를 하나 없애려고 한다. 이때 그 도시와 직접 연결된 고속도로도 함께 제거된다.

알고리즘 나라의 도시들은 가끔 정비가 필요하다. 정비에는 정비 기기가 필요하고, 도시마다 필요한 정비 기기의 최소 가격이 있다. 즉 한 도시에 필요한 정비 기기의 최소 가격이 x이면, 가격이 x 이상인 정비 기기를 사용해야 그 도시를 정비할 수 있다.

정비 기기는 고속도로를 통해서만 이동할 수 있다. 도시 정비는 긴급하지 않기 때문에, 고속도로로 연결된 도시들의 집합에는 한 대의 정비 기기만 사용된다.

당신은 정비 기기를 만드는 회사의 사장이다. 당신은 어떤 도시가 없어졌을 때 가장 매출이 높아지는지 분석하고 싶다. 매출은 알고리즘 나라의 모든 도시를 정비하는 데 필요한 최소 비용이다. 도시를 없앴을 때 가능한 가장 높은 매출을 출력하는 프로그램을 작성하여라.

첫째 줄에 양의 정수 N(2 ≤ N ≤ 1,000,000)이 하나 주어진다. 각 도시는 1 ~ N으로 번호가 하나씩 붙여져 있다. 그 다음 줄에는 1번 도시부터 N번 도시까지 필요한 정비 기기의 최소 가격이 차례대로 공백을 사이에 두고 N개의 양의 정수로 주어진다. 모든 가격의 합은 2³¹ 미만이다. 그 다음 줄부터 N-1개의 줄에는 고속도로가 연결하고 있는 두 도시의 번호를 의미하는 두 개의 정수가 한 줄에 공백을 사이에 두고 주어진다.

첫째 줄에 도시를 제거했을 때 가능한 가장 높은 매출을 출력한다.