Union Weight in Tree

Given a tree \(G\) with \(n\) nodes and \(n-1\) edges, where each edge has length \(1\) and the nodes are numbered from \(1\) to \(n\). Each node \(i\) has an associated weight \(W_i\). For every ordered pair of nodes \((u, v)\) such that the distance between \(u\) and \(v\) is exactly \(2\), a joint weight is produced defined as \(W_u \times W_v\).

Your task is to compute two values:

1. The maximum joint weight among all ordered pairs having distance exactly \(2\). If there is no valid pair, output \(0\).
2. The sum of all joint weights produced by the ordered pairs with distance exactly \(2\).

For any node \(x\) with at least two neighbors, any two distinct neighbors \(u\) and \(v\) will form two valid ordered pairs \((u, v)\) and \((v, u)\), each contributing \(W_u \times W_v\) to the sum.

Note: The answer for the maximum joint weight is taken over all valid ordered pairs in the tree.

inputFormat

The first line contains a single integer \(n\) representing the number of nodes in the tree.

The second line contains \(n\) integers \(W_1, W_2, \ldots, W_n\), where \(W_i\) is the weight of the \(i\)th node.

The following \(n-1\) lines each contain two integers \(u\) and \(v\) indicating that there is an edge connecting node \(u\) and node \(v\).

outputFormat

Output two integers separated by a space: the maximum joint weight among all ordered pairs with distance exactly \(2\), and the sum of all joint weights. If no valid pair exists, output 0 0.

sample

3
1 2 3
1 2
2 3

3 6