The main idea is to root the tree arbitrarily. For each node, we should encode both its parent and depth; for example, we could store the integer ~depth \times 100 + parent~. When answering a query, we can simply output the parent of whichever node is deeper, since this node is guaranteed to be on the path. If both nodes are equally deep, either node can be used. As there up to ~100 \times 100 = 10000~ unique states, this is only sufficient for ~25\%~ of the points. However, we can make the following optimizations:

Optimization 1a

Since queried nodes are not adjacent, their depths must either be equal or differ by at least ~2~. It suffices to store ~\lfloor \frac{depth}{2} \rfloor~ for each node, halving the number of unique states.

Optimization 1b

Set the parent of the root as ~1~. It actually suffices to store ~\lfloor \frac{\max(0, depth - 1)}{2} \rfloor~ for each node; this means that nodes at depth ~0~, ~1~, and ~2~ are mapped to the same value. This works because two nodes at these depths still have the property that the node with the larger stored integer is at least as deep as the other.

Optimization 2a

We can root the tree at the centre, to minimise the depth. In the worst case, the deepest node is at distance ~50~ away from the centre, so there are up to ~51~ unique depths that need to be represented. The reduces the number of unique states by ~49\%~.

Optimization 2b

In Optimization 2a, there will be ~51~ unique distances only in the case of a line graph. We can essentially root the tree at both central nodes. That is, instead of storing the depth of a node, we can store the minimum distance to either of the two central nodes. The parents for the central nodes do not matter.

For ~75\%~ of the points, it is sufficient to combine either Optimizations 1a and 2b, or Optimizations 1b and 2a. Note that Optimization 1b doesn't actually improve on Optimization 1a unless Optimization 2a is also used.

Optimization 3

Observe that a descending chain of nodes can have the same depth value if their parent values are increasing. Although this doesn't immediately help, we can use randomness to remap parent values, which decreases the expected maximum depth value.

For full points, combine the ideas from all three optimisations. In the context of Optimization 3, Optimization 1 allows adjacent nodes with the same depth value to violate the monotonicity property. Optimization 2 instructs that we should try all nodes as the root, not necessarily just the centre. The cutoff for full at ~D = 20~ is very generous, due to the nature of randomness leading to a range of possible values of ~D~.