For any given node, suppose the water we get from our parent is fixed. We have to press our lever to fill up the node. At what points do we stop?

We stop whenever any child (including non-direct child) fills up, at which point we recurse.

We stop whenever any child (including non-direct child) fills up, at which point we recurse. On a line, this means we get a complexity of ~\mathcal O(N!)~.

Specifically, we are pressing the current node's lever until a child fills up, and then summing the costs from all the children.

This is much like an algorithm that tries all amounts to push down, except since we are using floats, we have to determine the breakpoints ourselves.

There is also a simplex solution to this subtask, but it is useless for further subtask solving.

Let ~f_u(v)~ be the cost to satisfy node ~u~'s subtree assuming it is provided with ~v~ units of water from its parent. Based on subtask 1, what observations can we make about ~f_u~?

~f_u(v)~ is a piecewise function, since we have to re-calculate the costs every time a node fills. It is convex, since when a node fills up we always have more, not less, options for levers. Each of the pieces of the function is linear, since we are pressing a lever that fills linearly.

Slope trick.

We can represent the functions as a set of pairs, (change_point, slope_change). This definition means that when we add the functions (because this function is recursive), adding functions is equivalent to merging the sets.

Let ~F_u~ be the portion, as a decimal, of water that remains in node ~u~ when a lever is pushed.

Very large points will cause precision issues. How can we deal with them?

What if we delete large points and replace them with a flat section?

By deleting very large points (>~10^{50}~) and adding a constant to the answer, we can circumvent issues with precision.

Since the slopes get big very quickly, the sets get pruned quickly enough to achieve a good enough complexity.