Maximizing Army Morale

We are given a tree with (n) nodes representing armies. The nodes are connected by (n-1) edges and the tree is rooted at node 1. Each army (i) has a battle value (a_i) and an initial morale equal to (a_i). You can arbitrarily assign a secret code (either black or white) to each army. The morale update process is defined as follows:

When processing a node (u) (starting from the deepest nodes and moving upward), for every directly connected neighbor (v) with (\text{depth}(v)>\text{depth}(u)), if (v)'s secret code is the same as (u)'s secret code then (u) can contact (v) and must increase its morale by the sum of battle values of all armies in (v)'s subtree that have the same secret code as (v).

In other words, if an edge ((u,v)) (with (u) as the parent of (v)) has the same secret code on both ends, then (u)'s morale is increased by [ S(v)=\sum_{w\in\text{subtree}(v)\atop color(w)=color(v)}a_w. ]

The final total sum of morale is given by [ \text{Total}=\sum_{i=1}^{n}a_i+\sum_{(u,v)\text{ with same secret code}}S(v). ]

Your task is to choose the secret codes arbitrarily (i.e. assign black or white for each node) so that the total sum of the final morale values is maximized.

inputFormat

The input begins with an integer \(n\) (\(1\le n\le 10^5\)), the number of armies (nodes).
The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) where \(a_i\) is the battle value of the \(i\)-th army.
Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) meaning there is an edge connecting army \(u\) and army \(v\). It is guaranteed that the edges form a tree with node 1 as the root.

outputFormat

Output a single integer: the maximum total sum of morale values achievable after the updates.

sample

3
10 5 7
1 2
1 3

34