25428번 - 분필 도둑 서브태스크

수업 도중 분필이 부족한 적이 한 번씩은 있을 것이다. 단대소프트고에는 이에 대한 전설이 있다. 바로 분필 도둑 나홍칠이다.

놀랍게도 분필 도둑 나홍칠은 실제로 존재한다. 나홍칠이 분필을 훔치는 과정은 다음과 같다.

1. 먼저 교실 몇 개를 고른다. 고른 교실들은 모두 연결되어 있어야 한다. 즉 고른 교실 중 임의의 두 교실 $u$, $v$에 대하여, 고른 교실만을 지나서 $u$와 $v$ 사이를 오갈 수 있어야 한다.
2. 나홍칠은 모두에게 평등하기 때문에 선택된 교실들에서 모두 같은 양의 분필을 훔쳐 간다. 이때 원래 교실에 있는 분필의 양을 초과하는 분필을 가져가는 것은 불가능하다. 예를 들어 교실에 분필이 3개 있을 때 4개 이상의 분필을 훔치는 것은 불가능하다

단대소프트고는 교실 $N$개를 복도 $N-1$개로 연결한 형태로 되어있다. 또한 임의의 두 교실을 하나 이상의 복도를 통해 이동하는 방법이 존재한다.

나홍칠이 현재 상태에서 위 과정을 한번 실행 한다고 했을 때, 분필을 최대 몇 개 훔칠 수 있을지 구해보자.

첫째 줄에 교실의 수 $N$이 입력된다. $(1 ≤ N ≤ 100,000)$

둘째 줄에는 교실 $i$에 있는 분필의 수 $A_i$가 공백으로 구분되어 $N$개 입력된다. $(1 \leq A_i \leq 1,000,000)$

다음 $N-1$개 줄에는 교실 $u$와 교실 $v$가 복도로 연결되어 있음을 뜻하는 두 정수 $u$, $v$가 공백을 사이로 한 줄에 하나씩 입력된다. $(1 ≤ u, v ≤ N, u \ne v)$

첫째 줄에 나홍칠이 한 번에 훔칠 수 있는 최대 분필 수를 출력한다.