Since the number of edges that a mole can remove is one, it is possible to iterate through all the edges to calculate which edge needs to be added if we remove that edge.

Suppose we remove edge ~e = (a, b)~ and that doing so separates the tree into subtrees ~A~ and ~B~. Now we need to create a new edge ~e' = (a', b')~ where vertex ~a'~ is in subtree ~A~ and vertex ~b'~ is in subtree ~B~. There are many ways to do this to check them all.

Notice that the diameter of the new tree will be the largest of:

• The diameter of subtree ~A~, of length ~d(A)~;
• The diameter of subtree ~B~, of length ~d(B)~;
• The length of the longest path in subtree ~A~ rooted in ~a'~ plus the length of the longest path in subtree ~B~ rooted in ~b'~ plus one (for ~e'~).

The first two of these depend only on edge ~e~, the last on edge ~e'~. For this path to be as short as possible, we choose ~a'~ to be the halfway point on the diameter of subtree ~A~ and ~b'~ to be the halfway point on the diameter of subtree ~B~.

The length of the new path is then:

$$\displaystyle \left\lceil \frac{d(A)}{2} \right\rceil + 1 + \left\lceil \frac{d(B)}{2} \right\rceil$$

For each choice of edge ~e~, we can calculate the shortest diameter we can achieve if we remove that edge, and it is exactly:

$$\displaystyle \min\left\{d(A), d(B), \left\lceil \frac{d(A)}{2} \right\rceil + 1 + \left\lceil \frac{d(B)}{2} \right\rceil\right\}$$

So we need to calculate the diameters of both subtrees. The total number of subtrees we need to do this for is ~2(N-1)~, so we cannot afford a linear search for every subtree.

If we root the tree in any vertex, then subtrees isolated by removing edges from the tree can be divided into two groups – those not containing the root (call these subtrees "hanging") and those containing the root (call these "trimmed").

We can use dynamic programming to calculate the diameters of hanging subtrees. Let ~d_1(v)~ and ~d_2(v)~ be the two longest paths from vertex ~v~ to leafs in the tree. Then the diameter ~d(v)~ of the subtree rooted at ~v~ is easily calculated as:

$$\displaystyle d(v) = \max\{d_1(v)+d_2(v), \max\{d(w) : \text{for each child }w\}\}$$

The diameters of trimmed trees can also be found using dynamic programming. This time the recursive relation is more complex and calculated in the opposite order – from root to leaves.

Once we have calculated the diameters we can easily find which edge to remove. After this, we can find the halfway points on the diameters of subtrees to find which edge to add.

The overall complexity of the solution is ~\mathcal O(N)~.