P10212 [CTS2024] 众生之门

[原题面存档。](https://www.luogu.com.cn/paste/pd4a89g5)

给定 $n$、一棵 $n$ 个点的无向树和树上的两个不相同的节点 $s,t$，其中每条边的长度均为 $1$。节点由 $1$ 至 $n$ 的整数编号。记 $\mathrm{dist}(u,v)$ 表示 $u$ 和 $v$ 的距离（即简单路径经过的边数）。你需要给出一个 $1$ 到 $n$ 的排列 $p_1,p_2,\cdots,p_n$ 满足以下两个条件： - $p_1=s$，$p_n=t$； - 设 $d_i=\mathrm{dist}(p_i,p_{i+1})(1\leq i\leq n-1)$，那么你给出的排列需要满足以上条件的前提下，最小化 $\oplus_{i = 1} ^ {n - 1}d_i$，其中 $\oplus$ 表示按位异或。 如果有多种满足条件的排列，输出任意一种均可。

从标准输入读入数据。 本题有多组测试数据。第一行输入一个正整数 $T$ 表示测试数据组数。 对于每组数据，第一行输入三个正整数 $n,s,t$，接下来 $n-1$ 行每行两个正整数 $u,v$，表示地点 $u$ 和 $v$ 有直接无向道路连接（即树上的一条边）。

输出到标准输出。 对于每组数据，输出一行 $n$ 个正整数 $p_1,p_2,\cdots,p_n$，你需要保证其为 $1$ 到 $n$ 的一个排列且 $p_1=s$，$p_n=t$，且 $\oplus_{i = 1} ^ {n - 1} d_i$ 最小。

**样例 1 解释** 该样例共有三组测试数据。 - 对于第一组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $0$，样例输出为 $1,2,3$，其中 $d_1=d_2=1$。 - 对于第二组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $2$，样例输出为 $3,2,1,4$，其中 $d_1=d_2=1$，$d_3=2$；另一种合法输出为 $3,1,2,4$。 - 对于第三组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $1$，样例输出为 $1,5,3,4,2$，其中 $d_1=2$，$d_2=1$，$d_3=3$，$d_4=1$。 **样例 2 解释** 值得注意的是，该输入数据由所有满足 $n\leq 10$ 的，且所有不同 $s$ 和 $t$ 的相对位置的可能的树形态构成。 这个样例，无疑是善良的出题人无私的馈赠。中间忘了。出题人相信，这个美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。 ### 数据范围 设 $\sum n$ 表示单个测试点内所有数据的 $n$ 的和。对于所有测试数据， - $T≥1$； - $2\leq n\leq 5\times 10 ^4$，$\sum n\leq 5\times 10 ^ 5$； - $1\leq s,t\leq n$，$s\neq t$； - $1\le u,v\le n$，$u\neq v$； - 输入的 $n-1$ 个 $(u,v)$ 构成一棵树。 | 子任务编号 | $n$ | $\sum n$ | 特殊性质 | 分数 | |-------|-----------------------|-----------------------|------|----| | 1 | $\le 8$ | $\le 10^{3}$ | 无 | 5 | | 2 | $\le 12$ | $\le 10^{3}$ | 无 | 8 | | 3 | $\le 5 \times 10^{4}$ | $\le 5 \times 10^{5}$ | A | 17 | | 4 | $\le 5 \times 10^{4}$ | $\le 5 \times 10^{5}$ | B | 20 | | 5 | $\le 5 \times 10^{4}$ | $\le 5 \times 10^{5}$ | C | 17 | | 6 | $\le 10^{3}$ | $\le 10^{4}$ | D | 10 | | 7 | $\le 5 \times 10^{4}$ | $\le 5 \times 10^{5}$ | 无 | 23 | 特殊性质 A：保证每个点度数小于等于 $2$。 特殊性质 B：保证对于任意 $x$ 有 $\mathrm{dist}(s,x)+\mathrm{dist}(x,t)\le \mathrm{dist}(s,t)+2$。 特殊性质 C：保证 $\mathrm{dist}(s,t)=1$。 特殊性质 D：该子任务共有五个测试点，对于每一个测试点，保证 $T=10$ 且 $n=1000$，并且每个测试数据中，$s$ 在 $1\sim n$ 中等概率随机生成，$t$ 从 $1\sim n$ 除去 $s$ 中等概率随机生成，树从所有 $n$ 个点的有标号树中等概率随机生成。