*Note: the time limit for this problem is 4s, two times the default. The memory limit is also twice the default.*

Farmer John's farm has \(N\) barns (\(2 \leq N \leq 2\cdot 10^5\)) numbered
\(1 \dots N\). There are \(N-1\) roads, where each road connects two barns and it is
possible to get from any barn to any other barn via some sequence of roads.
Currently, the \(j\)th barn has \(h_j\) hay bales (\(1\le h_j\le 10^9\)).

To please his cows, Farmer John would like to move the hay such that each barn
has an equal number of bales. He can select any pair of barns connected by a
road and order his farmhands to move any positive integer number of bales less
than or equal to the number of bales currently at the first barn from the first
barn to the second.

Please determine a sequence of orders Farmer John can issue to complete the task
in the minimum possible number of orders. It is guaranteed that a sequence of
orders exists.

Problem credits: Aryansh Shrivastava

SCORING

• Test cases 2-8 satisfy \(N\leq 5000\)
• Test cases 7-10 satisfy \(v_i=u_i+1\)
• Test cases 11-16 satisfy no additional constraints

Problem credits: Aryansh Shrivastava

The first line of input contains the value of \(N.\)

The second line of input contains the space-separated values of \(h_j\) for
\(j = 1 \dots N\).

The final \(N-1\) lines of input each contain two space-separated barn numbers
\(u_i \ v_i\), indicating that there is a bidirectional road connecting \(u_i\) and
\(v_i\).

Output the minimum possible number of orders, followed a sequence of orders of
that length, one per line.

Each order should be formatted as three space-separated positive integers: the
source barn, the destination barn, and the third describes the number of hay
bales to move from the source to the destination.

If there are multiple solutions, output any.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > December > Silver