FarmCraft

Time limit3sMemory limit256 MB

Summary

Choose a tour of the tree from the root that visits every house and returns, so the latest moment of arrival plus install time is as early as possible.

Level: Medium7 of 10
Topics: Greedy, Tree, Sorting
Solved: No attempts yet

Problem

The village of Byteville has $n$ houses joined by $n-1$ roads. Between any two houses there is exactly one route. The houses are numbered from $1$ to $n$ , and house $1$ belongs to Byteasar, who runs the village.

A rural technology programme has delivered $n$ computers to Byteasar's house. Every house gets one computer, and Byteasar has to hand them out. The villagers have already agreed to start the latest version of FarmCraft together as soon as they have their machines.

Byteasar loads all the computers onto his pickup truck and sets off. He has exactly enough fuel to drive along each road twice. When he reaches a house he drops off one computer and drives on immediately. A household starts installing FarmCraft the moment its computer arrives. The install time differs from house to house and is known in advance. Byteasar installs the game on his own computer only after he has delivered everything and driven back home. Driving along one road takes $1$ minute, and unloading a computer takes no time.

Find the earliest moment at which every villager, Byteasar included, can start playing. That is, choose the delivery order that makes the last install finish as early as possible, and report that finishing time.

Input

The first line contains the number of houses in Byteville, $n$ . ( $2 \le n \le 500\,000$ )

The second line contains the integers $c_1, c_2, \dots, c_n$ separated by single spaces. $c_i$ is the install time in minutes for house $i$ . ( $1 \le c_i \le 10^9$ )

Each of the next $n-1$ lines describes one road. Such a line contains two integers $a$ and $b$ separated by a single space ( $1 \le a < b \le n$ ), meaning that a road runs directly between house $a$ and house $b$ .

Output

Print one integer on the first line: the earliest time, in minutes, at which the install has finished in every house, Byteasar's included.

Note

The picture below shows the village from the example.

If Byteasar delivers the computers in the order $3, 2, 4, 5, 6$ and then drives home, the installs in houses $1$ to $6$ finish after $11, 10, 10, 10, 8, 9$ minutes. Everyone starts playing after $11$ minutes.

If he delivers them in the order $3, 4, 5, 6, 2$ , the installs finish after $11, 16, 10, 8, 6, 7$ minutes, so nobody can start together until $16$ minutes have passed.

Examples9

Example 1
Input
```
6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6
```
Expected output
```
11
```
Example 2
Input
```
2
1 1
1 2
```
Expected output
```
3
```
Example 3
Input
```
2
1000000000 1000000000
1 2
```
Expected output
```
1000000002
```
Example 4
Input
```
5
1 7 6 5 4
1 2
1 3
1 4
1 5
```
Expected output
```
11
```
Example 5
Input
```
5
1 1 1 1 5
1 2
2 3
3 4
4 5
```
Expected output
```
9
```

Example 6

Input

6
1000 1 1 1 1 1
1 3
2 3
3 4
4 5
4 6

Expected output

Example 7

Input

7
1 1 1 1 1 1 1
1 2
1 3
2 4
2 5
3 6
3 7

Expected output

Example 8
Input
```
6
1 20 1 1 1 1
1 3
2 3
3 4
4 5
4 6
```
Expected output
```
22
```

Example 9

Input

8
2 1 1 1 1 1 1 40
1 2
2 3
3 4
4 5
5 6
6 7
7 8

Expected output