Maximum Weighted Depth Sum in Unicyclic Tree

You are given a tree with n nodes, numbered from 1 to n. Each node i has an associated weight w_i. You need to add one extra edge (that is not already present in the tree and is not a self‐loop) to form a unicyclic graph (i.e. a tree with exactly one cycle).

In the resulting graph, define the depth of a node to be its shortest distance to any node on the cycle. Note that the nodes on the cycle have depth 0. Formally, if we denote by dep_i the depth of node i in the unicyclic graph, your task is to add an edge so that the following sum is maximized:

For example, consider a tree with 4 nodes and weights [1,2,3,4] and edges: 1-2, 2-3, 3-4. By adding an edge between node 1 and node 3, the cycle becomes (1,2,3) and the depth of node 4 is 1, so the sum is 4 \(\times\) 1 = 4.

Your task is to compute the maximum possible sum.

inputFormat

The first line contains an integer n (number of nodes).

The second line contains n space‐separated integers, where the i-th integer is the weight w_i of node i.

Each of the following n-1 lines contains two integers u and v (1 ≤ u, v ≤ n) indicating there is an edge between nodes u and v.

You may assume that the input forms a tree and that n is small (for example, n ≤ 200).

outputFormat

Output a single integer, the maximum possible sum \(\sum_{i=1}^n w_i \times dep_i\) after adding an extra edge optimally.

sample

3
1 2 3
1 2
2 3

0