P15089 [UOI 2025 II Stage] OldPost --- NewPost

在 Trilyandia 国家，有 $n$ 个城市通过 $n-1$ 条道路相连。该国的道路系统很特别： - 每条道路仅连接两个不同的城市； - 任意两个城市之间最多有一条道路； - 从任意城市出发，都可以到达其他任意城市（可能需途经其他城市）。 邮政公司 OldPost 决定在该国提供配送服务。由于员工人数有限，运输仅沿一条长度为 $l$ 的路线 $a$ 进行，即一个城市序列 $a_1,a_2,\dots,a_l$，满足： - 对于 $i\neq j$，有 $a_i\neq a_j$； - 城市 $a_i$ 和 $a_{i+1}$ 之间有道路连接（$1\leq i < l$）。 为了最大化利润，OldPost 决定沿长度最长的路线运营。 OldPost 的古老竞争对手 NewPost 也决定做同样的事，但沿其自己的路线 $b$：$b_1,b_2,\dots,b_l$，该路线不一定与 $a$ 不同，但也具有最大可能长度。 总统得知两家公司的意图后，要求 OldPost 和 NewPost 选择路线 $a$ 和 $b$，使得覆盖的城市数量最多（即确保尽可能多的城市至少出现在一条路线上）。由于 Trilyandia 的总统擅长管理，而邮政公司擅长投递物品而非寻找路线，因此你需要找出这样的 $a$ 和 $b$。 注意，每家公司都希望自己的路线长度尽可能长；即使选择更短的路线能增加覆盖的城市总数。 请帮助找出具有最大可能长度且覆盖最多城市数量的路线 $a$ 和 $b$。

- 第一行包含一个整数 $n$（$2\leq n \leq 6\cdot 10^5$）——国家中的城市数量。 - 接下来的 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i,y_i \leq n, x_i \neq y_i$）——表示有道路连接的城市对。

- 第一行应包含一个整数 $l$（$2 \leq l \leq n$）——找到的贸易路线的长度。 - 第二行应包含 $l$ 个整数 $a_1,a_2,\dots,a_l$（$1 \leq a_i \leq n$）——路线 $a$ 中的城市。 - 第三行应包含 $l$ 个整数 $b_1,b_2,\dots,b_l$（$1 \leq b_i \leq n$）——路线 $b$ 中的城市。 如果有多个最优路线，输出任意一组即可。

:::align{center}  ::: 在示例中，可能的最长路线如下： - $5$-$4$-$3$-$2$-$6$-$7$ - $9$-$8$-$3$-$2$-$6$-$7$ - $5$-$4$-$3$-$2$-$1$-$10$ - $9$-$8$-$3$-$2$-$1$-$10$ 第一条和第四条路线可以覆盖所有城市。 ### 评分细则 - （$8$ 分）：$n\leq 10$； - （$8$ 分）：$n\leq 20$； - （$6$ 分）：$n \leq 1\,000$；恰好有一个城市直接与其他所有城市相连； - （$8$ 分）：$n \leq 20\,000$；恰好有两个城市只与另一个城市相连（城市呈链状）； - （$8$ 分）：$n \leq 20\,000$；恰好有一个城市与三个或更多城市相连； - （$8$ 分）：$n \leq 10\,000$；最多有 $10$ 个城市只与另一个城市相连； - （$16$ 分）：$n\leq 1\,000$； - （$18$ 分）：$n\leq 70\,000$； - （$20$ 分）：无额外限制。 翻译由 DeepSeek V3 完成