City Maintenance

Time limit2sMemory limit512 MB

Summary

Given a tree with a price on every vertex, find the maximum, over all choices of a removed vertex, of the sum of the maximum price within each remaining connected component.

Level: Hard8 of 10
Topics: Tree, DFS, Greedy, Implementation
Solved: No attempts yet

Problem

The country of Algorithm has $N$ cities and $N-1$ highways that connect them. Every city reaches every other city along the highways, directly or indirectly.

The country removes one city. When a city is removed, every highway attached to it disappears with it, and the removed city is no longer maintained.

Maintaining a city needs a maintenance machine. Each city has a minimum machine price. If a city's minimum price is $x$ , only a machine that costs $x$ or more can maintain that city.

A machine moves only along highways. City maintenance is not urgent, so one machine is used for each set of cities that the remaining highways still connect to one another.

You run the company that builds the machines. Your revenue is the smallest cost of maintaining every remaining city. Write a program that prints the highest revenue that removing one city can produce.

Input

The first line has a positive integer $N$ ( $2 \le N \le 10^6$ ). The cities are numbered 1 through $N$ .

The second line has the minimum machine price of city 1 through city $N$ in order, separated by spaces. Every price is a positive integer, and the sum of all prices is less than $2^{31}$ .

Each of the next $N-1$ lines has the numbers of the two cities that one highway connects, separated by a space.

Output

Print the highest revenue that removing one city can produce.

Examples4

Example 1
Input
```
4
1 3 7 4
1 3
2 3
3 4
```
Expected output
```
8
```
Example 2
Input
```
2
5 9
1 2
```
Expected output
```
9
```
Example 3
Input
```
5
1 2 3 4 5
1 2
2 3
3 4
4 5
```
Expected output
```
8
```
Example 4
Input
```
5
1 5 6 7 8
1 2
1 3
1 4
1 5
```
Expected output
```
26
```