Explanation

In order for each barn to have the same number of hay bales, each barn must have the average number of bales. Also, in any optimal solution, there will be at most one order for each edge.

Thus, we can DFS from an arbitrary root. At each node, we calculate the number of bales the barn needs to either transport from its children to its parent or the number of bales it needs to transport from its parent to its children, and store this as an order.

However, we also need to make sure that we print a valid ordering of these orders, so that a barn does not have negative hay bales at any moment. To do this, we keep track of the incoming and outgoing orders for each node, and construct a directed graph of these. Then, DFS from any unvisited node, and recurse on every barn that the node has an incoming order from (that hasn't been visited). Finally, print the barn's outgoing orders.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
const int MAX_N = 2e5;

using ll = long long;
using pll = pair<ll, ll>;