DMOPC '16 Contest 1 P4 - Tree Appraisal

View as PDF

Points: 15 (partial)
Time limit: 1.8s
Memory limit: 256M

Author:
Problem type

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. ()

For this section of the data only, .

For this section of the data only, .

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 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