옛날 제가 만들었다는 문제 보니까 도저히 읽을 수 없네요.

나름 번역을 시도해보았습니다. 혹시 이 번역본이 이해하기 편하다면 교체해주실 수 있나요?

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

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

알고리즘 나라의 도시들은 가끔 정비가 필요하다. 정비에는 정비 기기가 필요하다. 각 도시는 정비에 필요한 정비 기기의 최소 가격이 있다. 물론 더 비싼 정비 기기를 사용해도 상관 없다. 정비 기기는 고속도로를 통해서만 이동할 수 있다. 도시 정비는 긴급한 것이 아니다. 그래서 고속도로로 연결된 도시들의 집합에는 한 대만 있어도 충분하다.

따라서 도시를 하나 없애게 되면 고속도로로 연결된 트리가 여러 개 생길 수 있고, 그에 따라 여러 대의 정비 기기가 필요할 수 있다.

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

입력

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

출력

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