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 ui to city vi.
Each city has some facility value fi 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≤ 105 ) the number of cities of country S.
The next lines contains N integers separated by single spaces fi (-105 ≤ fi ≤ 105 ) 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 |