Arboris Contractio

The goal is not to make the tree “pretty”. The goal is to minimize the diameter, and then use as few operations as possible to reach that best possible diameter.

For $n=2$, the only tree has diameter $1$, so the answer is $0$.

For $n\ge 3$, the minimum possible diameter of any tree is $2$: diameter $1$ would mean only two vertices, while a star on $n$ vertices has diameter $2$. So we need the minimum number of operations needed to turn the tree into some star.

Understanding one operation

Suppose we want the final star to be centered at vertex $r$.

If we choose $s=r$ and some endpoint $t$, then the operation takes the whole path

$$r=v_0, v_1, \dots, v_k=t$$

and connects every $v_i$ directly to $r$.

So one operation can make all vertices on one simple path from $r$ become direct children of $r$.

That is the key. It does not magically fix multiple branches at once. If a subtree splits into two branches, one path can go down only one of them. The other branch needs another operation somewhere. Classic tree nonsense.

Fix a center $r$

Root the tree at $r$.

A vertex is already fine if it is $r$ or directly adjacent to $r$. Every other vertex needs to eventually become adjacent to $r$.

Now look at the rooted tree. Each operation starting from $r$ can follow one downward path and fix all vertices at distance at least $2$ that lie on that path. Therefore, we need to cover all non-adjacent vertices using downward chains.

A very useful way to count this is to look at the number of leaves after rooting at $r$.

Every operation can end at one leaf and fix the whole path from $r$ to that leaf. If a leaf is already adjacent to $r$, it needs no operation. Otherwise, that leaf must be the endpoint of some operation, because it has no descendant that could drag it along later.

So, for a chosen center $r$, the needed operations are exactly the number of leaves whose distance from $r$ is at least $2$.

Now translate that into degrees.

In the original tree, leaves are exactly vertices with degree $1$. A leaf is adjacent to $r$ exactly when it is one of $r$'s leaf neighbors. Thus:

$$\text{operations}(r)=\text{total leaves}-\text{leaf neighbors of }r.$$

So to minimize operations, choose $r$ with as many leaf neighbors as possible.

Let $L$ be the number of leaves in the tree, and let

$$mx = \max_r \#\{\text{leaf neighbors of }r\}.$$

Then the answer is

$$\boxed{L-mx}.$$

This also handles the tiny cases naturally. For $n=2$, both vertices are leaves, each has one leaf neighbor, so $L-mx=2-1=1$, but the diameter is already minimal and no operation is needed. So we special-case $n=2$ with answer $0$.

Why the formula is correct

Lower bound: after choosing the final center $r$, every leaf not adjacent to $r$ must be touched by some operation. Since it is a leaf, the only way to make it adjacent to $r$ is for an operation path to end at it. One operation has only one endpoint $t$, so it can handle at most one such leaf. Therefore, we need at least

$$L-\text{leaf neighbors of }r$$

operations.

Upper bound: for every leaf not adjacent to $r$, perform one operation from $r$ to that leaf. This makes every vertex on that path adjacent to $r$. After doing this for all such leaves, every vertex is adjacent to $r$: any non-center vertex lies on a path from $r$ to some leaf, and if it was not already adjacent, it gets fixed when that leaf is processed.

So the lower bound is achievable. Pick the best center, and we are done.

The solution is just counting leaves and finding the vertex with the most leaf neighbors. Very rude problem statement for such a tiny implementation, honestly.