Limits 2s, 512 MB

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 .

Input

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

Output

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

Samples

InputOutput
5
-4 10 10 10 -10
1 2
1 3
1 4
2 5
26
InputOutput
3
-3 -5 -10
1 2
1 3
0
InputOutput
8
2 -3 5 10 4 1 4 -5
1 3
1 2
3 7
3 4
4 8
2 6
2 5

23

Submit

Login to submit.

Statistics

43% Solution Ratio
sohel_secEarliest, Jun '22
sohel_secFastest, 0.0s
sohel_secLightest, 9.7 MB
sohel_secShortest, 1035B
Toph uses cookies. By continuing you agree to our Cookie Policy.