Maximum Accumulated Power in a Rooted Tree

HansBug has a rooted tree with N nodes (each representing an "aaa") and each node has an associated power value. The tree has exactly N - 1 edges and is rooted at node 1. For each node i, consider the team consisting of node i and every node in its subtree (i.e. all descendants of i). HansBug plans to process each team in a sequential "continuation" order, where the j-th processed node in the team contributes an amount equal to the sum of the power values of the first j nodes in that ordering.

More precisely, if a team of size n is ordered as \(v_1, v_2, \dots, v_n\) (where \(v_k\) is the power value of the node placed at position k), the score obtained from that team is \[ \sum_{i=1}^{n} \left(\sum_{j=1}^{i} v_j\right) = v_1 \times n + v_2 \times (n-1) + \cdots + v_n \times 1. \] It is clear that to maximize this score for a fixed team, the nodes should be ordered by their power values in non‐increasing order (i.e. sorted descending).

Your task is to compute the maximum total score HansBug can achieve, where the total score is defined as the sum over all nodes (each node \(i\) contributes the maximum possible score from its corresponding team/subtree when its members are optimally ordered).

Note: No node will have more than 5 direct children.

inputFormat

The first line contains a single integer N \( (1 \leq N \leq 10^5)\) representing the number of nodes in the tree.

The second line contains \(N\) integers \(v_1, v_2, \dots, v_N\) where \(v_i\) is the power value of node \(i\). Each \(v_i\) is an integer (\(|v_i| \leq 10^9\)).

The following N - 1 lines each contain two integers u and v representing an edge between nodes u and v.

outputFormat

Output a single integer which is the maximum total accumulated score HansBug can obtain by optimally ordering the teams of each node's subtree.

sample

3
1 2 3
1 2
1 3

19