DMOPC '16 Contest 1 P4 - Tree Appraisal

View as PDF

Submit solution

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Suppose there is a tree with N nodes (numbered from 1 to N), which is a graph with N nodes, N-1 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 i has a value of K_i.

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 a to b 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 a to b is not considered distinct from one which goes from b to a. Formally, find the total of appraise(a,b) across all pairs (a,b), where 1 \le a < b \le N, and the appraise function is as described.

Input Specification

On the first line, there will be one integer N.
On the second, there will be N space separated integers from K_1 to K_N. These indicate the values of nodes of the tree in increasing order.
On the subsequent N-1 lines, there will be two integers, a_j and b_j, such that a_j is not equal to b_j. This indicates an undirected edge going between a_j and b_j.

Constraints

1 \le N \le 200\,000

0 \le K_i \le 1000

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. (2^{63}-1)

20% Subtask:

For this section of the data only, 1 \le N \le 100.

35% Subtask:

For this section of the data only, 1 \le N \le 2000.

The remaining 45% of the data has 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 Output 2

The tree has four nodes, connected in a line: 3 - 2 - 4 - 1, and the values have been assigned as 585 for node 3, 843 for node 2, 569 for node 4, and 618 for node 1. Therefore, there are six paths we must consider:

  • 3 \to 2 with sum 1428 and length 1;
  • 3 \to 4 with sum 1997 and length 2;
  • 3 \to 1 with sum 2615 and length 3;
  • 2 \to 4 with sum 1412 and length 1;
  • 2 \to 1 with sum 2030 and length 2;
  • 4 \to 1 with sum 1187 and length 1.

Thus, the answer is the following: 1428 * 1 + 1997 * 2 + 2615 * 3 + 1412 * 1 + 2030 * 2 + 1187 * 1, which is equal to 19926.

Sample Input 3

5
0 1 1 1 1
1 2
1 3
1 4
1 5

Sample Output 3

28

Comments


  • 2
    imaxblue  commented on Oct. 11, 2016, 4:55 p.m.

    do I mod anything?


    • 3
      k_53P  commented on Oct. 11, 2016, 5:32 p.m. edit 2

      You don't need to worry about overflow, it is guaranteed that the answer will be less than 2^{63}-1. (statement updated)