Suppose there is a tree with nodes (numbered from
to
), which is a graph with
nodes,
edges, no cycles, and exactly one available path to travel between any pair of nodes. In this tree, each node is made of something which is probably really valuable, and therefore node
has a value of
.
You are interested in inspecting the tree in a specific way in order to extract its monetary value. A path is a sequence of nodes such that each node after the first is connected to the previous node by an edge, and no node is visited more than once. Suppose that there is a path from to
in the tree. The appraised value, in unmarked moneys, of that path will be equal to:
the path's length (equal to one less than the number of nodes included in the path)
…multiplied by:
the sum of the values of all nodes included in the path
In order to determine how many unmarked moneys you can get from a tree, you must find the sum of the appraised values of all distinct pairwise paths in the tree. A path going from to
is not considered distinct from one which goes from
to
. Formally, find the total of
across all pairs
, where
, and the
function is as described.
Input Specification
On the first line, there will be one integer .
On the second, there will be space separated integers from
to
. These indicate the values of nodes of the tree in increasing order.
On the subsequent lines, there will be two integers,
and
, such that
is not equal to
. This indicates an undirected edge going between
and
.
Constraints
It is recommended to use 64-bit integers. It is guaranteed that the answer will not exceed the upper limit of a 64-bit signed integer. ()
Subtask 1 [20%]
Subtask 2 [35%]
Subtask 3 [45%]
No additional constraints.
Output Specification
Print a single integer, the sum of the appraisal values of all distinct paths in the tree.
Sample Input 1
2
3 4
1 2
Sample Output 1
7
Sample Input 2
4
618 843 585 569
3 2
1 4
2 4
Sample Output 2
19926
Explanation for Sample Output 2
The tree has four nodes, connected in a line: , and the values have been assigned as
for node
,
for node
,
for node
, and
for node
. Therefore, there are six paths we must consider:
with sum
and length
;
with sum
and length
;
with sum
and length
;
with sum
and length
;
with sum
and length
;
with sum
and length
.
Thus, the answer is the following: , which is equal to
.
Sample Input 3
5
0 1 1 1 1
1 2
1 3
1 4
1 5
Sample Output 3
28
Comments
beautiful!
do I mod anything?
You don't need to worry about overflow, it is guaranteed that the answer will be less than
. (statement updated)