# Problem C

Gasqutvå

Gasquen is antiquated so Gasqutvå shall now be crowdfunded by the Chalmers students. The $N$ students communicate along a tree where the students are nodes. Students are arbitrarily numbered from $1$ to $N$. The $i$th student’s generosity is described by one integer $a_ i$. You are to choose the first student to donate to the campaign, who will begin by donating $100$ kr and then tell their neighbours in the tree about the campaign. When a student $i$ tells a neighbour $j$ about the campaign, and student $j$ hasn’t already donated, they will donate $d_ j=d_ i+a_ j$ kr where $d_ i$ is the amount $i$ donated. Student $j$ will then go on to tell their neighbours in the tree about the campaign. Which student should donate first to maximize the total amount raised?

## Input

The first line of input contains one integer $2 \leq N$, the number of students in the tree. Each of the following $N$ lines contains one integer $0 \leq a_ i \leq 10^9$ describing how generous the $i$th student is. After that, each of the following $N-1$ lines contains two integers $1\leq i, j \leq N$ denoting that students $i$ and $j$ are neighbours in the tree. It is guaranteed that the connections form a tree.

## Output

Print the number of the student that should donate first to maximize the total amount raised. If there are multiple suitable students, choose the one with the lowest number.

## Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group |
Points |
Constraints |

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

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

Sample Input 1 | Sample Output 1 |
---|---|

3 50 60 100 2 1 1 3 |
2 |