Distance Matching
Contest: Codeforces Round 666 (Div. 1)
Difficulty rating: 3200
Tags: constructive algorithms, dfs and similar, trees

You are given an integer $$$k$$$ and a tree $$$T$$$ with $$$n$$$ nodes ($$$n$$$ is even).

Let $$$dist(u, v)$$$ be the number of edges on the shortest path from node $$$u$$$ to node $$$v$$$ in $$$T$$$.

Let us define a undirected weighted complete graph $$$G = (V, E)$$$ as following:

- $$$V = \{x \mid 1 \le x \le n \}$$$ i.e. the set of integers from $$$1$$$ to $$$n$$$
- $$$E = \{(u, v, w) \mid 1 \le u, v \le n, u \neq v, w = dist(u, v) \}$$$ i.e. there is an edge between every pair of distinct nodes, the weight being the distance between their respective nodes in $$$T$$$

Your task is simple, find a perfect matching in $$$G$$$ with total edge weight $$$k$$$ $$$(1 \le k \le n^2)$$$.

Input format:
The first line of input contains two integers $$$n$$$, $$$k$$$ ($$$2 \le n \le 100\,000$$$, $$$n$$$ is even, $$$1 \le k \le n^2$$$): number of nodes and the total edge weight of the perfect matching you need to find.

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) denoting an edge between $$$v_i$$$ and $$$u_i$$$ in $$$T$$$. It is guaranteed that the given graph is a tree.

Output format:
If there are no matchings that satisfy the above condition, output "NO" (without quotes) on a single line.

Otherwise, you should output "YES" (without quotes) on the first line of output.

You should then output $$$\frac{n}{2}$$$ lines, the $$$i$$$-th line containing $$$p_i, q_i$$$ ($$$1 \le p_i, q_i \le n$$$): the $$$i$$$-th pair of the matching.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
A tree is a connected acyclic undirected graph.

A matching is set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex.

A perfect matching is a matching which matches all vertices of the graph; that is, every vertex of the graph is incident to exactly one edge of the matching.

Example input:
4 2
1 2
2 3
3 4

Example output:
YES
2 1
3 4

Example input:
4 4
1 2
2 3
3 4

Example output:
YES
3 1
2 4

Editorial:
Root the tree at centroid $$$c$$$.
First, determine if there is any matching that satisfies the requirement. Consider an edge $$$e$$$ that splits the tree into $$$2$$$ subtrees with sizes $$$x$$$ and $$$N - x$$$ respectively, let $$$z$$$ be the number of paths passing through $$$e$$$, then we have $$$z$$$ has the same parity as $$$x$$$ and $$$x \% 2 \le z \le min(x, N - x)$$$. Thus the necessary condition for a matching is $$$\sum (sub(v) \% 2) \le K \le \sum sub(v)$$$ and $$$K$$$ has the same parity as $$$\sum sub(v)$$$, where $$$v \ne c$$$ and $$$sub(v)$$$ is the size of the subtree rooted at $$$v$$$. We prove that this is also the sufficient condition by its construction:
Consider the matching with maximum $$$K$$$, note that $$$c$$$ lies on all the paths in the matching.
We can see that if we remove two vertices from the largest subtree, rooted at $$$w \ne c$$$, then $$$c$$$ is still the centroid. Also, if we match two vertices $$$v$$$ and $$$u$$$ in the subtree rooted at $$$w$$$, the answer decreases by $$$2 \cdot dist(c, lca(u, v))$$$. Based on this, we can achieve the target $$$K$$$ by repeating the following operation ($$$currentK$$$ is the current maximum possible $$$K$$$, initially $$$\sum sub(v)$$$):
• Let $$$z$$$ be a non-leaf vertex in the largest subtree such that $$$dist(c, z) \le \frac{currentK - targetK}{2}$$$ (if there are many $$$z$$$, take any $$$z$$$ with maximum $$$dist(c, z)$$$). Match two vertices $$$v$$$ and $$$u$$$ whose LCA is $$$z$$$, then remove $$$v$$$ and $$$u$$$ from the tree.
After some time $$$currentK = targetK$$$, so we just need to greedily match the remaining vertices to create the final matching.
The final complexity is $$$O(N log N)$$$.