Distance Matching

题意翻译

- 给定一棵 $n(n\rm ~is ~even)$ 个点的树 $T$ 以及常数 $k$。现生成一张 $n$ 个点的完全图 $G$，对于每对点 $(u,v)$ 连接一条边权为 $\textrm{dist}(u,v)$ 的边。其中 $\textrm{dist}(u,v)$ 定义为树 $T$ 中 $u\to v$ 之间的边数。 - 你需要求这张图的一个完美匹配使得边权和恰好为 $k$；输出一组方案或确定不存在解。 - 完美匹配的定义是：一组边集，满足每个点都恰好被覆盖一次。 - $n\le 10^5,k\le n^2$

题目描述

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) $ .

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

4 2
1 2
2 3
3 4

输出样例 #1

YES
2 1
3 4

输入样例 #2

4 4
1 2
2 3
3 4

输出样例 #2

YES
3 1
2 4

说明

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.

题意翻译

- 给定一棵 $n(n\rm ~is ~even)$ 个点的树 $T$ 以及常数 $k$。现生成一张 $n$ 个点的完全图 $G$，对于每对点 $(u,v)$ 连接一条边权为 $\textrm{dist}(u,v)$ 的边。其中 $\textrm{dist}(u,v)$ 定义为树 $T$ 中 $u\to v$ 之间的边数。 - 你需要求这张图的一个完美匹配使得边权和恰好为 $k$；输出一组方案或确定不存在解。 - 完美匹配的定义是：一组边集，满足每个点都恰好被覆盖一次。 - $n\le 10^5,k\le n^2$