IOI 2010 day2 2- K-pop star(Traffic) > 문제은행 : 정보올림피아드&알고리즘




2547 : K-pop star(Traffic)

제한시간
1000 ms   
메모리제한
0 MB   
해결횟수
3 회   
시도횟수
19 회   

문제

세계적으로 K-pop 열풍이 불고 있다. 당신은 K-pop 콘서트를 N개의 국가 중 한 곳에서 개최하려고 한다. 

각 나라 사이에는 비행기로 이동할 수 있는 왕복항로가 N-1개 존재하고,

어느 두 국가를 정해도, 한 국가에서 다른 국가까지 가는 방법은 정확히 한 가지 있다. 

K-pop 콘서트를 개최한 이후, K-pop 콘서트를 보고 다시 자국으로 돌아가려는 사람들로 북적일 것이다.


K-pop 콘서트가 끝나고 생기는 공항의 혼잡을 줄이기 위해, 혼잡 점수를 최소가 되게 하려고 한다. 

 

이 때, 혼잡 점수는 사람이 가장 많이 지나가는 항로의 사람 수와 같다. 

 

이 때, N과 각 국가에서 K-pop 콘서트를 볼 사람들의 수가 주어질 때, 

혼잡 점수가 최소가 되게 K-pop 콘서트의 개최 위치를 정하는 프로그램을 작성하여라.

 


모든 사람의 수가 20억을 넘지 않는다.

 

 

[입력 예 그림 설명]

 


 


입력형식

첫 번째 줄에는 국가의 수 N(1≤N≤1,000,000)이 주어진다.
두 번째 줄에는 각 국가에서 K-pop 콘서트를 볼 사람들의 수가 주어진다.
다음 줄에서부터 N-1개의 줄에는 각 국가 간의 항로가 주어진다. 이 때, 국가 번호는 0 이상 N-1 이하이다.


출력형식

K-pop 콘서트를 개최하는 국가의 번호를 출력한다. 답이 여러 개이면 그 중 아무거나 출력한다.


입력 예

5
10 10 10 20 20 
0 2
1 2
3 2
4 3

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP