(Analysis by Claire Zhang)

If every barn has the same number of haybales in the end, each must have the average. Let's subtract the average from each $h_i$ for convenience; now our objective is to make $h_i=0$ for all $i$.

For each edge, consider the two subtrees resulting from erasing this edge. If the sum of either subtree is non-zero, this edge must be used to transport some haybales. Thus, our answer is at least the number of such edges. In fact, this lower bound is achievable using a recursive algorithm.

First, root the tree arbitrarily. Let $sum(x)$ be the sum of $x$’s subtree (including $x$). When we call $distribute(x)$, we distribute the haybales in $x$’s subtree so that each node is left with $0$ haybales, except possibly the root, which will have $sum(x)$ haybales. We implement $distribute(x)$ as follows:

1. $distribute(k^+)$ for all children $k^+$ of $x$ such that $sum(k^+)\geq 0$.
2. Transport $sum(k^+)$ haybales across $(k^+, x)$.
3. Transport $-sum(k^-)$ haybales across $(x, k^-)$ for children $k^-$ such that $sum(k^-)<0$.
4. $distribute(k^-)$ for all $k-$.

Note we only move haybales that exist in this reformulation because after we move haybales from $i$, $i$ still has at least $average$ haybales (we never make $h_i$ negative). Also, when we call $distribute(x)$ our algorithm guarantees $sum(x)\geq 0$, ensuring the feasibility of step 2. Critically, each edge is used at most once - when its parent is called - and we only move haybales across edge $u$ to $v$ if $sum(u)>0$. Therefore, $distribute(root)$ executes an optimal sequence of orders.

Aryansh Shrivastava's code ($distribute$ is implemented as dfs_make_orders):

#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

using ll = long long;

vector<ll> h, subtree_tot;

ll avg;
vector<tuple<int, int, ll>> orders; // {source, destination, bales}

void dfs_fill_subtrees(int node = 0,
int par = 0) { // root tree arbitrarily at 0
// fill in total bales in each subtree and size of each subtree
subtree_tot[node] = h[node] - avg;
if (child != par) {
dfs_fill_subtrees(child, node);
subtree_tot[node] += subtree_tot[child];
}
}

void dfs_make_orders(int node = 0, int par = 0) { // root tree arbitarily at 0
// give from child to node
if (child != par) {
if (subtree_tot[child] >= 0) dfs_make_orders(child, node);
if (subtree_tot[child] > 0)
orders.emplace_back(child, node, subtree_tot[child]);
}
// give from node to child
if (child != par && subtree_tot[child] < 0) {
orders.emplace_back(node, child, -subtree_tot[child]);
dfs_make_orders(child, node);
}
}

int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
for (ll &t : h) cin >> t, avg += t;
avg /= n;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v, --u, --v;