This problem features an algorithm called central decomposition.

Definition (centroid):
For a tree, the vertex \(v\) is called a centroid if:

• when \(v\) is the root, any subtree rooted at \(v\)’s child has a size at most half the size of the original tree.

Theorem (existence of centroid):
Every tree has one or two centroids.

Proof:
We can find by the following algorithm.

• From the tree \(T\), choose an arbitrary vertex \(r\), and find the size of subtrees rooted at each vertex.
• Initialize \(v\) with \(r\).
• Repeat the following:
  • Check if every subtree rooted at \(v\)’s child has a size at most half the size of \(T\).
    • If so, terminate the algorithm by determining that \(v\) is the centroid.
    • Otherwise, replace \(v\) with the child of \(v\) with the maximum subtree size.

We justify this algorithm. The depth of \(v\) increases every iteration, so it is obvious that this algorithm terminates. Suppose that \(u\) was found by the algorithm. We show that \(u\) satisfies the condition of centroid. Since the last iteration did not stop, the size of subtree rooted at \(u\) (when \(r\) is the very root of \(T\)) is greater than half the size of \(T\), so the size of \(T\) except for the subtree rooted at \(u\) is strictly less than half the size of \(T\). Also, now that the iteration has stopped, every subtree rooted at \(u\)’s child (when \(r\) is the very root of \(T\)) has a size at most half the size of \(T\). Hence, when \(T\) is rooted at \(u\), every subtree rooted at \(u\)’s child has a size at most half the size of the original tree, thus \(u\) is a centroid. ∎

Now consider the following problem. We rephrase the second condition as follows: for all vertices \(v\) except for the leaves, the size of every subtree rooted at \(v\)’s child is at most half the size of the subtree rooted at \(v\).

Let the tree \(T\) rooted at its centroid \(v\). Also, let \(S_i\) be the connected components of the forest obtained by removing \(v\) from \(T\).

Then the following conditions hold:

• In \(T\), if \(x\)-\(y\) path contains \(v\), such a pair satisfies the first condition. Otherwise, \(x\) and \(y\) belongs to the same \(S_i\).
  
• The second condition with respect to \(v\) is satisfied no matter how the edges of \(S_i\) and the edge connecting \(T\) and \(S_i\) are changed.
  

Therefore, it is sufficient to solve the same problem as the original for each \(S_i\). Since a size-\(1\) tree obviously satisfies the problem, it can be solved recursively.

One can a the centroid in an \(O(\#vertices)\) time, and every recursion halves the size of the tree, so there are at most \(O(\log N)\) steps of recursion, and thus the problem is solved in a total of \(O(N\log N)\).

Note the conditions are satisfied if, but not only if, \(R\) is a centroid decomposition of \(T\). Sample Output 1 is a valid non-centroid-decomposition answer.

Bonus: how can you judge if an answer to this problem is valid?