Present Panic

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 1.0s

Java 2.5s

Python 2.5s

Memory limit: 128M

Author:

ji_mmyliu

Problem types

It is Christmas Eve, and Santa is delivering presents!

There are $N$ ~N~ houses in the world which he has already delivered presents to. Each house $i$ ~i~ has already been delivered $a_i$ ~a_i~ presents. However, he noticed that he gave some houses more presents than others. He wants all the houses to end up with the same number of presents.

Thankfully, Santa has unlimited elves at his disposal. The houses are connected by $N-1$ ~N-1~ two-way roads where each house is able to reach every other house through some series of roads. A single elf can carry a present from any house to a house adjacent to it (i.e. the elf can only carry the present across $1$ ~1~ road). Presents may be carried multiple times, and multiple presents can be carried across a single path.

What is the minimum number of elves needed to distribute the presents evenly?

Constraints

For all test cases, $1 \le N \le 10^5$ ~1 \le N \le 10^5~, $0 \le a_i \le 10^9$ ~0 \le a_i \le 10^9~, the sum of all $a_i$ ~a_i~ for $1 \le i \le N$ ~1 \le i \le N~ is divisible by $N$ ~N~.

Subtask 1 [10%]

$1 \le N, a_i \le 5$ ~1 \le N, a_i \le 5~

Subtask 2 [10%]

$1 \le N, a_i \le 16$ ~1 \le N, a_i \le 16~

Subtask 3 [30%]

$1 \le N, a_i \le 10^3$ ~1 \le N, a_i \le 10^3~

Subtask 4 [50%]

No additional constraints.

Input Specification

First line: $N$ ~N~ (the number of houses).

Second line: $N$ ~N~ space-separated integers describing $a_i$ ~a_i~ for each $1 \le i \le N$ ~1 \le i \le N~ (the initial number of presents in each home).

Next $N-1$ ~N-1~ lines: Two space-separated integers $u_i$ ~u_i~ and $v_i$ ~v_i~ ( $1 \le u_i, v_i \le N$ ~1 \le u_i, v_i \le N~) indicating that a road connects houses $u_i$ ~u_i~ and $v_i$ ~v_i~.