Practice on Toph

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

Police Stations

By sohel_sec · 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 (-105fi ≤ 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

Discussion

Statistics


NaN% Solution Ratio

Submit

Login to submit

Related Contests

SEC Intra Campus Programming Contest, CSE Fest 2020 Ended at 2020-02-19 11:02:00 +0000 UTC