Maximum Gold Collection in a Tree

You are given a tree of N cities. Each city i has an associated amount of gold denoted by \(g_i\). The tree is represented by N-1 edges connecting the cities. A traveler can start at any city and is allowed to re-visit cities (although the gold in each city can only be collected once) to travel between cities. The traveler wants to maximize the total collected gold. Since the traveler is allowed to backtrack, it is always possible to visit every city. Hence, the maximum gold that can be collected is simply the sum of the gold in all cities.

Task: Compute and output the maximum amount of gold that can be collected.

Note: The input graph is guaranteed to be a tree (i.e. it is connected and has no cycles).

inputFormat

The first line contains an integer N representing the number of cities. The second line contains N integers \(g_1, g_2, \ldots, g_N\) where \(g_i\) is the amount of gold in the i-th city. Each of the following N-1 lines contains two integers \(u\) and \(v\), indicating there is an edge connecting city \(u\) and city \(v\).

outputFormat

Output a single integer, the maximum amount of gold that can be collected.

5
1 2 3 4 5
1 2
1 3
2 4
2 5

15