Say that identifies when a mole at can locate from its distance alone. On a path, one endpoint identifies every location. Otherwise, let be the leaves and the locations identified by no leaf. Deploying at is optimal.
For each directed edge , let be the greatest distance from within its component after deleting , and that component's diameter. A nonleaf is identified by a leaf exactly when some neighbor satisfies .
Compute these values by rerooting. Among branch heights for neighbors and two zeros, take the largest two, . Then
Retaining the three largest branch heights and two largest branch diameters makes excluding one neighbor constant-time. Compute values from children to parents, then from parents to children. Select all leaves and nonleaves having no qualifying neighbor. Time and space complexity are .
Proof
Suppose identifies . Let be the neighbor of toward , and the component containing after deleting . Then
A farther location inside would yield another location at distance along its path. Thus is a diameter endpoint of ; the opposite endpoint is an original leaf that also identifies . Conversely, if is a diameter endpoint, the opposite endpoint identifies . This gives the criterion . It also shows that every location in requires its own mole.
For each leaf, consider its path up to but excluding the first branching vertex. A mole outside this path cannot distinguish its last vertex from a vertex on another branch. Each such path therefore needs a mole. These paths are disjoint and identified by their respective leaves, hence disjoint from . This proves the lower bound , attained by .
The rerooting recurrence follows because a diameter stays within one branch or joins two through . Its length is therefore the maximum of the branch diameters and the sum of the two greatest branch heights.
