Deriving an upper bound of the solution

Define the contribution of an edge \(i\) of \(T\) in a matching as the number of pairs in the matching that strides over edge \(i\). Then, the weight of the matching coincides the sum of the contributions of the edges. (This idea is called preposterous trick.)

Based on this rewording, let us consider an upper bound of the maximum matching. Removing an edge \(i\) from \(T\) splits \(T\) into two subtrees. If they have \(c_i\) and \((N-c_i)\) edges, the contribution of edge \(i\) never exceeds \(\min\{c_i,N-c_i\}\). Thus, the weight of the matching is at most \(\displaystyle \sum_{i=1}^{N-1} \min\{c_i,N-c_i\}\).

Constructing a solution that achieves the upper bound

There exists a matching that achieves this upper bound. Intuitively, one can match vertices so that they stride over the “center”. (You may come up with this idea by imaging the case where the tree is a path or a star.)

There is a concept called centroid which corresponds to the “center” of a tree. A centroid \(g\) of a tree \(T\) is a vertex such that by removing \(g\), every resulting subtree has a weight of \(\lfloor N/2 \rfloor\) or less. Every tree has a centroid, and it can be found in \(O(N)\) time with Depth First Search (DFS). For more details on centroid, the following article may help:

• article by drken (in Japanese, but with some illustrations): ツリーの重心分解 (木の重心分解) の図解 (Illustration of centroid decomposition of tree)

Using a centroid, one can find a matching achieving the upper bound by the following algorithm.

1. Find a centroid \(g\) of the tree \(T\).
2. Let \(T_1,T_2,\dots,T_k\) be the subtrees obtained by removing \(g\) from \(T\) and thus splitting into several subtrees.
3. Construct an array \(A\) consisting of (all vertices of \(T_1\)), (all vertices of \(T_2\)), …, and (all vertices of \(T_k\)).
4. If \(N\) is an even number, add \(g\) to the tail of \(A\).
5. For each \(i=1,2,\dots,\lfloor N/2 \rfloor\), match vertices \(A_i\) and \(A_{i+\lfloor N/2 \rfloor}\).

Proof of validity

We will show that the matching obtained by this algorithm achieves the upper bound.

First, for each pair \((A_i,A_{i+\lfloor N/2 \rfloor})\) of this matching, we will show that \(A_i\) and \(A_{i+\lfloor N/2 \rfloor}\) belong to different subtrees (where \(g\) is regarded as belonging to \(T_0\)). If they are in the same subtree, then all of \(A_i,A_{i+1},\dots,A_{i+\lfloor N/2 \rfloor}\) belong to the same centroid, which means the subtree contains at least \(\lfloor N/2 \rfloor + 1\) vertices; this contradicts to the assumption that \(g\) is a centroid.

Next, if all the pairs belong to different subtrees, then the weight of that matching achieves the upper bound. Regard \(T\) rooted at \(g\). For each edge \((u_i,v_i)\) (without loss of generality, assume that \(u_i\) is the parent of \(v_i\)), every vertex \(x\) contained in the subtree rooted at \(v_i\) is contained in a pair \((x,y)\). Since \(x\) and \(y\) belong to different subtrees, the \(x-y\) path always passes through edge \(i\). Therefore, edge \(i\) contributes as many times as the number of the vertices in the subtree of \(v_i\); this is the maximum achievable contribution.

Sample code (PyPy)