Traffic Congestion

Time limit3sMemory limit256 MB

Summary

Pick the tree city that minimizes the largest number of fans traveling on any single road when all fans leave the arena city.

Level: Medium4 of 10
Topics: Tree, DFS
Solved: No attempts yet

Problem

Canada is a large country, but many areas have no residents and most people live near the southern border. The Trans-Canada Highway, completed in 1962, runs 7,821 km from St. John's in the east to Victoria in the west and connects the people living in that narrow strip of land.

Canadians like hockey. After a game, thousands of fans get into their cars and drive home, and the roads jam. A wealthy entrepreneur wants to buy a hockey team and build a new arena. Choose where to build it so that the traffic congestion after a game is as small as possible.

The country consists of cities joined by roads. Every road is bidirectional, and exactly one route connects any pair of cities. A route between cities $c_0$ and $c_k$ is a sequence of distinct cities $c_0, \dots, c_k$ such that a road joins $c_{i-1}$ and $c_i$ for every $i$ . The arena is built in one city, called the arena city. After a game, every fan except those who already live in the arena city travels from the arena city to their home city. The congestion on a road is proportional to the number of fans that travel along it. Pick the arena city so that the number of fans on the most congested road is as small as possible.

Input

The first line contains the number of cities $N$ . Cities are numbered from $0$ to $N-1$ .

The second line contains $N$ integers $P_0, \dots, P_{N-1}$ , where $P_i$ is the number of hockey fans living in city $i$ .

Each of the next $N-1$ lines contains two integers $S$ and $D$ , meaning that a road joins city $S$ and city $D$ .

Output

Print the number of the arena city on one line. If several cities give the same minimum for the most congested road, print the smallest such city number.

Constraints

$1 \le N \le 200\,000$
$1 \le P_i$
$P_0 + \dots + P_{N-1} \le 2\,000\,000\,000$
The $N-1$ roads connect all cities, and exactly one route joins any pair of cities.

Hint

Removing the arena city splits the country into pieces. The road that leaves the arena city toward one piece carries exactly the fans who live in that piece.

Examples7

Example 1
Input
```
6
1 2 3 4 5 6
0 1
1 2
1 3
3 4
3 5
```
Expected output
```
3
```
Example 2
Input
```
4
1 1 1 1
0 1
1 2
2 3
```
Expected output
```
1
```
Example 3
Input
```
1
7
```
Expected output
```
0
```
Example 4
Input
```
2
5 9
1 0
```
Expected output
```
1
```
Example 5
Input
```
5
1 100 100 100 100
0 1
0 2
0 3
0 4
```
Expected output
```
0
```
Example 6
Input
```
5
1 1 1 1 1000
0 1
1 2
2 3
3 4
```
Expected output
```
4
```

Example 7

Input

7
3 1 4 1 5 9 2
0 1
1 2
2 3
3 4
4 5
5 6

Expected output