CF1396E Distance Matching

给定一个整数 $k$ 和一棵有 $n$ 个节点的树 $T$（$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$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i, u_i \le n$），表示树 $T$ 中的一条边。保证给定的图是一棵树。

如果不存在满足条件的匹配，输出一行 "NO"（不带引号）。 否则，第一行输出 "YES"（不带引号）。 接下来输出 $\frac{n}{2}$ 行，每行两个整数 $p_i, q_i$（$1 \le p_i, q_i \le n$），表示匹配中的一对节点。

树是一个连通且无环的无向图。 匹配是指一组两两不相邻的边，且没有自环；即没有两个边共享同一个顶点。 完美匹配是指匹配覆盖了图中所有顶点；即每个顶点恰好属于匹配中的一条边。 由 ChatGPT 4.1 翻译