시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 158 51 28 27.184%

문제

심심한 kcm1700은 도시의 도로망이 집과 집을 이어주는 Tree 형태(즉, 길의 수는 집의 수보다 한 개가 적으며 모든 집은 서로 이어져 있음)로 되어있음을 악용하여 자신의 라이벌인 kcm1303을 견제하기로 하였다.

현재 kcm1303은 출장 팥빙수 회사의 사장이고 이제 막 사업을 시작하려 한다. 그 회사의 직원들은 팥빙수 제조기를 들고 직접 주문자의 집을 찾아가서 팥빙수를 만드는 일을 하고 있다. kcm1700은 어떤 적당한 한 집을 사서 그 회사의 직원들이 팥빙수를 들고 통과하지 못하도록 하려 한다. 팥빙수 제조기를 들고 그의 집을 통과하려고 하면 팥빙수 제조기는 kcm1700에 의해 망가질 것이다. kcm1700이 어떤 집을 구입하여 길을 막게 되면 kcm1303은 어쩔 수 없이 팥빙수 제조기를 여러 개 만들어야 할 수도 있다. 팥빙수 제조기가 kcm1700이 구입한 집을 지나가는 것이 불가능하기 때문에 한 개만 구입해서는 모든 주문자에게 팥빙수를 만들어 줄 수 없는 경우가 있기 때문이다. (kcm1303은 모든 고객에게 서비스를 제공하고 싶어한다. 물론 kcm1700이 구입한 집은 빼고 ^^)

팥빙수 제조기는 규모 별로 가격이 다르다. 각 집마다 필요로 하는 규모가 다른데, 비싼 팥빙수 제조기를 사면 싼 팥빙수 제조기가 필요한 집에서도 쓸 수 있다. 돈이 별로 없는 kcm1303은 kcm1700의 방해에도 불구하고 최소한의 비용을 써서 팥빙수 제조기를 만들어야 한다. kcm1700, kcm1303 두 명 모두 각 집이 요구하는 최소한의 팥빙수 제조기의 규모를 알고 있다.

kcm1700이 kcm1303을 잘 견제하도록 도와주자. 적당한 한 집을 사서 팥빙수 제조기를 구입하는 최소의 비용이 최대가 되도록 만들고, 그 때의 비용을 출력하는 프로그램을 작성하여라.

입력

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

출력

첫째 줄에 팥빙수 제조기를 구입하는 최소의 비용이 최대가 될 때 비용을 출력한다.

예제 입력 1

4
1 3 7 4
1 3
2 3
3 4

예제 출력 1

8

힌트

kcm1700이 2번 집을 구입한다면 7의 비용을 들여 팥빙수 제조기를 구입하면 되지만, kcm1700이 3번 집을 구입하면 1+3+4=8의 비용을 지불해야 한다. 팥빙수 제조기가 kcm1700의 집을 통과하지 못하기 때문이다.

출처

Contest > koi4u > koi4u 2008년 5월 모의고사 C번