교통 혼잡

캐나다는 국토가 넓지만 사람이 살지 않는 지역이 많고, 인구는 대부분 남쪽 국경 근처에 모여 산다. 1962년에 완공된 대륙 횡단 고속도로는 동쪽 끝 세인트존스에서 서쪽 끝 빅토리아까지 7,821 km를 이으며, 이 좁고 긴 땅에 사는 사람들을 연결한다.

캐나다 사람은 하키를 좋아한다. 경기가 끝나면 수천 명의 팬이 차를 타고 집으로 돌아가서 도로가 크게 막힌다. 한 사업가가 하키 팀을 사고 새 경기장을 지으려고 한다. 경기가 끝난 뒤의 교통 혼잡이 가장 작아지도록 경기장을 지을 도시를 골라야 한다.

나라는 도시와 도시를 잇는 도로로 이루어진다. 도로는 모두 양방향이고, 서로 다른 두 도시를 잇는 경로는 정확히 하나뿐이다. 도시 $c_0$과 $c_k$를 잇는 경로란 서로 다른 도시를 나열한 $c_0, \dots, c_k$이며, 모든 $i$에 대해 $c_{i-1}$과 $c_i$ 사이에 도로가 있다. 경기장은 도시 하나에 짓고, 그 도시를 경기장 도시라고 부른다. 경기가 끝나면 경기장 도시에 사는 팬을 뺀 나머지 팬이 모두 경기장 도시에서 자기 도시로 이동한다. 각 도로가 얼마나 막히는지는 그 도로를 지나는 팬 수에 비례한다. 가장 많이 막히는 도로를 지나는 팬 수가 최소가 되도록 경기장 도시를 정해야 한다.

첫째 줄에 도시의 수 $N$이 주어진다. 도시 번호는 $0$부터 $N-1$까지이다.

둘째 줄에 $N$개의 정수 $P_0, \dots, P_{N-1}$이 주어진다. $P_i$는 $i$번 도시에 사는 하키 팬 수이다.

이어지는 $N-1$개의 줄에는 도로를 나타내는 두 정수 $S$와 $D$가 주어진다. $S$번 도시와 $D$번 도시를 잇는 도로가 있다는 뜻이다.

경기장 도시의 번호를 한 줄에 출력한다. 가장 많이 막히는 도로의 팬 수를 똑같이 최소로 만드는 도시가 여러 개이면, 그중 번호가 가장 작은 도시를 출력한다.

• $1 \le N \le 200\,000$
• $1 \le P_i$
• $P_0 + \dots + P_{N-1} \le 2\,000\,000\,000$
• 주어지는 $N-1$개의 도로는 모든 도시를 연결하고, 서로 다른 두 도시를 잇는 경로는 하나뿐이다.

경기장 도시를 빼면 나라는 여러 덩어리로 나뉜다. 경기장 도시에서 어느 덩어리로 나가는 도로가 감당하는 팬 수는 그 덩어리에 사는 팬 수와 같다.