Always interesting when a random solution is better than a deterministic solution, though it may very well mean that we don’t know the best metric yet.

After reading this, my intuition would be to try to construct a tree where those loose ends are as close together as possible, but yeah, even if this were a better approach, actually proving it, that seems to be a whole different story.