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:
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; vector<vector<int>> adj; 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; for (int child : adj[node]) 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 for (int child : adj[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 for (int child : adj[node]) 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; h.resize(n), adj.resize(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; adj[u].emplace_back(v), adj[v].emplace_back(u); } subtree_tot.resize(n); dfs_fill_subtrees(); dfs_make_orders(); cout << size(orders) << "\n"; for (auto [u, v, b] : orders) cout << ++u << " " << ++v << " " << b << "\n"; }