P14369 [JOISC 2018] 路网服务 / Road Service

**这是一道提交答案题。如果希望直接提交答案的生成代码，请确保它不会运行超过 20 秒。** IOI 王国有 $N$ 座城市，编号从 $1$ 到 $N$。此外还有 $N - 1$ 条双向道路，编号从 $1$ 到 $N - 1$。第 $i$ 条道路连接第 $A_i$ 座城市和第 $B_i$ 座城市。任意两座城市之间均存在路径。 两座城市之间的距离定义为连接它们的最少道路数。IOI 王国的总距离定义为所有不同城市对之间距离的总和。 IOI 王国的国王计划修建 $K$ 条额外的道路，以减少总距离并提升便利性。 你作为国王的助手，需帮助国王制定一个良好的修建方案。 **任务** 给定 IOI 王国现有道路的信息以及待修建道路的数量，输出一个修建 $K$ 条道路的方案。总距离越小，你获得的分数越高。

本任务共有 6 个输入。请从每个输入中读取以下数据： - 输入第一行包含三个以空格分隔的整数 $N$、$K$ 和 $W_0$。这表示 IOI 王国有 $N$ 座城市，国王计划修建 $K$ 条道路，$W_0$ 是评分参数。 - 接下来的 $N - 1$ 行中，第 $i$ 行（$1 \le i \le N - 1$）包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 条道路连接的城市。

在提交文件中写入 $K$ 行。 输出的第 $j$ 行包含两个整数 $X_j$、$Y_j$（$1 \le X_j \le N$，$1 \le Y_j \le N$），表示待修建道路所连接的两座城市。

### 数据范围 所有输入数据满足以下条件： - $1 \le N \le 1000$。 - $1 \le A_i < B_i \le N$（$1 \le i \le N - 1$）。 - $(A_i, B_i) \ne (A_k, B_k)$（$1 \le i < k \le N - 1$）。 - 任意两座城市之间均存在路径。 ### 评分规则 对于每个输入，你的得分按如下方式计算： 若你的输出不符合格式要求，则得分为零分。否则，设按你的方案修建道路后，总距离为 $W$，该输入对应的满分为 $P$。我们定义： $$ S = 1.0 - \frac{W}{W_0} $$ 那么，你在此输入中获得的得分为： $$ \min(P, P \times 20^S) $$ 本任务的总分为所有输入得分之和，四舍五入取最接近的整数。 各输入数据对应的 $N$、$K$、$W_0$、$P$ 值如下表所示： | 输入数据 | $N$ | $K$ | $W_0$ | $P$ | |:--------:|:----:|:----:|:--------:|:---:| | $1$ | $20$ | $4$ | $512$ | $10$ | | $2$ | $1000$ | $100$ | $2650000$ | $18$ | | $3$ | $1000$ | $300$ | $1755000$ | $18$ | | $4$ | $1000$ | $100$ | $2900000$ | $18$ | | $5$ | $1000$ | $100$ | $2690000$ | $18$ | | $6$ | $1000$ | $300$ | $1745000$ | $18$ | 翻译由 Qwen3-235B 完成。