← All solutions

The problem is probably most easily solved by binary search for the answer. However, checking whether it is possible to achieve a certain answer X is a bit tricky.

There are a few different ways of checking this, ranging from quite complicated dynamic programming solutions to the more elegant direct solution described below. An important parameter in the runtime of all these solutions is what the maximum value of X can be. It is a nice (but surprisingly difficult) exercise to prove that, no matter what the size of the tree is, X does not have to be larger than 118 (the significance of this number is of course that it is 59 · 2, and that 59 is the maximum possible rounding error on a single edge).

Root the tree arbitrarily, and consider some vertex v of the tree. Let us say that an interval [ a, b] is permissible for v if the edges in the subtree rooted at v can be rounded in such a way that:

• Every path in the subtree has an error of at most X.
• Every path in the subtree which ends in v has an error which lies in the interval [ a, b].

Note that a permissible interval must have a ≤ 0 and b ≥ 0. Furthermore, let us say that an interval [ a, b] is redundant for v if there is some b0 < b such that [ a, b0 ] is permissible.

Now, checking whether it is possible to achieve a maximum error of X is equivalent to checking whether there exists some permissible error for the root of the tree. We will do this by computing the set of all non-redundant permissible intervals for each node v. Fix some node v, let c be its number of children, and for i between 0 and c, let Ti denote the subtree rooted at v but including only the first i children of v. Suppose [ a, b] is a non-redundant permissible interval for Ti−1 , and that [ a0 , b0 ] is a non-redundant permissible interval for the subtree rooted at the i’th child of v, and that the error for the edge from v to its i’th child can be chosen as e (there are always one or two possible values for e). Then if a + a0 + e and b + b0 + e both are of absolute value at most X, [min( a, a0 + e), max(b, b0 + e)] is a permissible interval for Ti . All non-redundant permissible intervals for Ti can be constructed this way, but also some redundant ones. In order to keep the list of intervals short (of order X rather than order X 2 ), one should prune away the redundant ones.