# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Recently the government of country S is going to construct some police stations(possibly zero) in some cities of his countries. As the terrorists and robbers are always ready to ruin the countries peace. There are **N** cities in the country, numbered from **1** to **N**, connected only by exactly **N - 1** roads. The i-th road connects city **u**_{i} to city **v**_{i}.
Each city has some facility value **f**_{i} the facility value can be negative. To build a police station at city v is the sum of facility values all cities which are directly connected to city **v** (including v)**Note that you can not count a facility value of a city more than once.**

As you are a dedicated programmer, the government recruits you to calculate the maximum possible sum of facility value .

First line contains a single integer **N**(1 ≤ **N**≤ 10^{5} ) the number of cities of country S.

The next lines contains **N** integers separated by single spaces **f**i (-10^{5} ≤ **f**i ≤ 10^{5} ) facility value of city i (**1**≤ i ≤ **N**)

Each of the following **N - 1** lines contains two integers u and v (1≤u,v≤N) denoting that there is an edge between **u** and **v**

Print – one integer the maximum possible sum of facility value.

Input | Output |
---|---|

5 -4 10 10 10 -10 1 2 1 3 1 4 2 5 | 26 |

Input | Output |
---|---|

3 -3 -5 -10 1 2 1 3 | 0 |

Input | Output |
---|---|

8 2 -3 5 10 4 1 4 -5 1 3 1 2 3 7 3 4 4 8 2 6 2 5 | 23 |