(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;
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() {
    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);
    cout << size(orders) << "\n";
    for (auto [u, v, b] : orders) cout << ++u << " " << ++v << " " << b << "\n";