← 返回题目列表

Codeforces · 1396/E

E. 距离匹配

中文机器翻译题面 查看原题

给定一个整数 $$$k$$$ 和一棵树 $$$T$$$,其节点为 $$$n$$$($$$n$$$ 为偶数)。

设 $$$dist(u, v)$$$ 为 $$$T$$$ 中从节点 $$$u$$$ 到节点 $$$v$$$ 的最短路径上的边数。

让我们定义一个无向加权完全图 $$$G = (V, E)$$$ 如下:

- $$$V = \{x \mid 1 \le x \le n \}$$$ 即从 $$$1$$$ 到 $$$n$$$ 的整数集
- $$$E = \{(u, v, w) \mid 1 \le u, v \le n, u \neq v, w = dist(u, v) \}$$$ 即每对不同节点之间都有一条边,权重是 $$$T$$$ 中各自节点之间的距离

你的任务很简单,在 $$$G$$$ 中找到一个完美匹配,总边权为 $$$k$$$ $$$(1 \le k \le n^2)$$$。

输入

输入的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$2 \le n \le 100\,000$$$, $$$n$$$ 是偶数, $$$1 \le k \le n^2$$$):你需要找到的完美匹配的节点数和总边权重。

以下 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$v_i$$$,$$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) 表示 $$$T$$$ 中 $$$v_i$$$ 和 $$$u_i$$$ 之间的边。保证给定的图是一棵树。

输出

如果没有满足上述条件的匹配项,则单行输出“NO”(不带引号)。

否则,您应该在输出的第一行输出“YES”(不带引号)。

然后你应该输出 $$$\frac{n}{2}$$$ 行,第 $$$i$$$ 行包含 $$$p_i, q_i$$$ ($$$1 \le p_i, q_i \le n$$$):第 $$$i$$$ 匹配对。

示例

输入 #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

注意

树是连通的非循环无向图。

匹配是成对不相邻边的集合,其中没有一个是循环;也就是说,没有两条边共享公共顶点。

完美匹配是匹配图的所有顶点的匹配;也就是说,图的每个顶点都恰好与匹配的一条边相关联。