For each edge, consider how many times it contributes to the score. An upper bound is the size of the smaller of the two subtrees created when the edge is cut.

In fact, this upper bound can be achieved. First, treat the input tree as a rooted tree with the centroid \(R\) as the root. Let \(v_1, v_2, \cdots, v_k\) be the direct children of the root, and \(T_1, T_2, \cdots, T_k\) be their respective subtrees. It suffices to choose leaves from two different subtrees and remove them, except for the last operation.

Assume that the root is initially matched with \(v_1\). Then, in the first operation, leaves of \(T_1\) and \(T_j\) (\(j \neq 1\)) must be chosen. After this operation, the root will be matched with \(v_j\). Then, \(T_j\) is chosen next, and so on. If, each time you choose \(T_j\), you choose the \(T_j\) with the largest size, then you can finish all operations. However, this only guarantees that the number of vertices in each subtree is valid; it does not ensure that the leaves can be taken properly.

Despite this explanation, it is actually possible to remove leaves within each subtree. This can be done by considering the vertices top-down from the root. Assume that we are now focusing on vertex \(v\). If the vertex matched with \(v\) is a child of \(v\), then a leaf from that child’s subtree must be chosen. Otherwise, choose some child and select a leaf from its subtree. Continuing this process eventually leads to a leaf, which can then be removed.

While the procedure for selecting appropriate leaves has been explained, if leaves are removed one by one, the worst-case total time complexity would be \(O(N^2)\). However, by slightly modifying the above procedure, you can find an efficient order to remove each vertex as a leaf. Specifically, you can perform a DFS that prioritizes edges used in the matching and use the vertices along the postorder traversal.

By implementing the above procedures, this problem can be solved in \(O(N\log N)\) time.

Sample Code (C++)