DMOPC '16 Contest 1 P4 - Tree Appraisal - Olympiads Online Judge

DMOPC '16 Contest 1 P4 - Tree Appraisal

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.8s

Memory limit: 256M

Author:

k_53P

Problem type

Suppose there is a tree with $N$ $N$ nodes (numbered from $1$ $1$ to $N$ $N$ ), which is a graph with $N$ $N$ nodes, $N-1$ $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$ $i$ has a value of $K_i$ $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$ $a$ to $b$ $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$ $a$ to $b$ $b$ is not considered distinct from one which goes from $b$ $b$ to $a$ $a$ . Formally, find the total of $appraise(a,b)$ $a p p r a i s e (a, b)$ across all pairs $(a,b)$ $(a, b)$ , where $1 \le a < b \le N$ $1 \leq a < b \leq N$ , and the $appraise$ $a p p r a i s e$ function is as described.

Input Specification

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

Constraints

$1 \le N \le 200\,000$ $1 \leq N \leq 200 000$

$0 \le K_i \le 1000$ $0 \leq K_{i} \leq 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$ $2^{63} - 1$ )

Subtask 1 [20%]

$1 \le N \le 100$ $1 \leq N \leq 100$

Subtask 2 [35%]

$1 \le N \le 2000$ $1 \leq N \leq 2000$

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

Copy

2
3 4
1 2

Sample Output 1

Copy

Sample Input 2

Copy

4
618 843 585 569
3 2
1 4
2 4

Sample Output 2

Copy

Explanation for Sample Output 2

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

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

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

Sample Input 3

Copy

Sample Output 3

Copy

Comments

0

Shoot commented 58 days ago

beautiful!

3

imaxblue commented on Oct. 11, 2016, 8:55 p.m.

do I mod anything?

4

k_53P commented on Oct. 11, 2016, 9: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$ $2^{63} - 1$ . (statement updated)