CF1423C Dušan's Railway

如你所知，Dušan 喜欢玩铁路模型。他有一张包含若干城市的地图，这些城市通过铁路相连。可以将他的地图看作一个图，其中顶点表示城市，铁路表示边。到目前为止，他的地图对应的图是一棵树。你应该知道，树是一个连通且无环的无向图。 他很好奇自己的铁路网络是否可以进一步优化。他想要添加所谓的“捷径”，即连接一对城市的新铁路。这条捷径代表了树中这对城市之间的唯一路径上的所有铁路。由于 Dušan 不喜欢重复经过同一条铁路，他还在新网络中定义了“好路径”。注意，添加捷径后，图不再是一棵树。他称一条路径为好路径，当且仅当没有哪一条边在路径中出现超过一次，无论是作为原有铁路边，还是被某条捷径代表的边（在好路径中，每条捷径的长度为 1，但它所代表的所有边都被占用，不能在该路径中再次出现）。在定义了好路径后，他将两座城市之间的好距离定义为它们之间最短好路径的长度。最后，他将网络的“捷径直径”定义为任意两座城市之间的最大好距离。 现在他想知道，是否有可能通过添加尽量少的捷径，使得捷径直径不超过 $k$。 你的方案添加的捷径数量不得超过 $10 \cdot n$。

输入的第一行包含两个整数 $n$（$1 \le n \le 10^4$），表示 Dušan 的铁路地图中的城市数量，以及 $k$（$3 \le k \le n$），表示他希望实现的捷径直径。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \neq v_i$），表示城市 $u_i$ 和 $v_i$ 之间有一条铁路。

输出的第一行包含一个整数 $t$，表示添加的捷径数量。 接下来的 $t$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示在城市 $u_i$ 和 $v_i$ 之间添加一条捷径。

注意，如果在所有城市和城市 1 之间都添加一条捷径，图论意义上的直径会变成 2。然而，这样得到的路径可能不是好路径，因为某些边可能会被重复使用。在示例中，如果对所有城市和城市 1 添加捷径，并不能得到一个有效的方案，因为对于城市 5 和 10，使用捷径 5-1 和 1-10 的路径不是好路径，因为边 1-2、2-3、3-4、4-5 会被重复使用。 由 ChatGPT 4.1 翻译