Little Gena Loves to solve problems, but this time she has a tough task to solve. After spending lot of time she came to you and ask for your help. now it's your turn to solve this. You are given a un directed graph of N cities with N-1 roads. it's possible to get from any city to any other city. you are also given a array beauty of size N. On this graph you can perform the following type of operation:
Choose any road and destruct it. From the resulting two graphs keep one and discard the other.
You are allowed to perform as many operations as you want (possibly none, at most N-1). In the end the beauty of the Graph left is computed as the sum of beauty[degree(city)], for each city of the graph. You need to maximize this beauty of graph.
Note: degree of a particular city is number of roads that are connected to it.
Input:
The first line contains a single integer N representing the number of cities of the graph.
The second line contains N values representing the elements of beauty (0-indexed).
Each of the next N-1 lines contains two integer values, representing two cities that are connected by road.
Output:
The output should contain a single integer representing maximum beauty you can get.
Constraints :
1 <= N <= 10^5
-10^9 <= beauty[i] <= 10^9
Author: Mohib Manva
You can get 10 by deleting(destructing) all edges remaining only vertex 0. So now as there is no edge degree of vertex 0 after deleting is 0. So beauty value is beauty[0] which is 10.
EXPLANATION
please read the problem statement carefully, after destroying a road you will left with two sub graphs from which you have to discard one. so after every operation you will have one graph.
In a sample test case, Initially we had graph with vertexes[1,2,3,4], now delete road 1-3, so we will have two sub graphs G1 = [1,2,4] and G2 = [3] , discard sub graph G1 so you will left with Graph G2 which has only one vertex which has a beauty = 10 (because degree of vertex 3 is 0) which is maximum possible.
