Problem H
Dalarna

Dalarna’s road network consists of $N$ cities and $N-1$ roads. Each road directly connects two cities. If a taxi is in a city, it can travel to all cities that are directly connected to it via a road. Furthermore, the network is constructed so that it is always possible to travel between any pair of cities using one or more roads.

For each city $i$, Harry needs to ensure that at least $p_i$ taxis pass through the city to meet his goal. A taxi travels between two specified cities in the network and follows the shortest path.

To avoid raising suspicion, Harry wants to use as few taxis as possible. Help him calculate the minimum number of taxis he needs to order to meet the requirements.

Input

The first line contains an integer $N$ ($1 \leq N \leq 10^5$), the number of cities in Dalarna.

The second line contains $N$ integers $p_1, p_2, ..., p_N$ ($0 \leq p_i \leq 10^9$), where $p_i$ indicates the number of taxis that must pass through city $i$.

The next $N-1$ lines describe the roads between the cities. Each line contains two integers $u$ and $v$ ($1 \leq u, v \leq N$), indicating that there is a road between city $u$ and city $v$. The road network connects all cities.

Output

Print a single integer: the minimum number of taxis Harry needs to order.

Scoring

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

Figure 1: The road network for the 6 cities in sample 3.

Figure 2: A possible solution for sample 3, where the blue, orange, purple, green, and red paths represent 5 different taxi routes.

3
3 1 5
1 2
2 3

5

4
1 2 2 2
1 3
4 2
3 2

2

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

5