Gasqutvå

Gasquen은 낡았으므로 이제 Chalmers 학생들이 Gasqutvå를 크라우드펀딩해야 한다. $N$명의 학생은 학생들을 정점으로 하는 트리를 따라 소통한다. 학생들에게는 $1$부터 $N$까지 임의로 번호가 매겨져 있다. $i$번째 학생의 관대함은 하나의 정수 $a_i$로 나타낸다. 캠페인에 가장 먼저 기부할 학생을 선택해야 한다. 이 학생은 먼저 $100$ kr를 기부한 다음 트리에서 자신의 이웃들에게 캠페인에 관해 알린다. 학생 $i$이 이웃 $j$에게 캠페인에 관해 알렸고 학생 $j$이 아직 기부하지 않았다면, 그 학생은 $i$이 기부한 금액을 $d_i$이라 할 때 $d_j=d_i+a_j$ kr를 기부한다. 그런 다음 학생 $j$은 트리에서 자신의 이웃들에게 캠페인에 관해 계속 알린다. 모금된 총액을 최대화하려면 어느 학생이 가장 먼저 기부해야 하는가?

채점

제출한 풀이는 각각 일정한 점수가 배정된 테스트 그룹들로 평가된다. 한 테스트 그룹의 점수를 얻으려면 해당 테스트 그룹의 모든 테스트 케이스를 해결해야 한다. 최종 점수는 단일 제출에서 얻은 점수 중 최댓값이다.

그룹 | 점수 | 제약 조건

$1$ |$60$| $N \leq 100$

$2$ |$40$| $N \leq 10^5$

입력의 첫째 줄에는 트리에 있는 학생 수를 나타내는 하나의 정수 $2 \leq N$이 주어진다. 이어지는 $N$개의 각 줄에는 $i$번째 학생이 얼마나 관대한지를 나타내는 하나의 정수 $0 \leq a_i \leq 10^9$이 주어진다. 그다음 이어지는 $N-1$개의 각 줄에는 학생 $i$과 $j$이 트리에서 이웃임을 나타내는 두 정수 $1\leq i, j \leq N$가 주어진다. 연결 관계가 트리를 이룬다는 것이 보장된다.

모금된 총액을 최대화하기 위해 가장 먼저 기부해야 하는 학생의 번호를 출력한다. 적합한 학생이 여러 명이면 번호가 가장 작은 학생을 선택한다.