{"problem":{"name":"[CTS2024] 众生之门","description":{"content":"给定 $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$； -","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10212"},"statements":[{"statement_type":"Markdown","content":"给定 $n$、一棵 $n$ 个点的无向树和树上的两个不相同的节点 $s,t$，其中每条边的长度均为 $1$。节点由 $1$ 至 $n$ 的整数编号。记 $\\mathrm{dist}(u,v)$ 表示 $u$ 和 $v$ 的距离（即简单路径经过的边数）。你需要给出一个 $1$ 到 $n$ 的排列 $p_1,p_2,\\cdots,p_n$ 满足以下两个条件：\n\n- $p_1=s$，$p_n=t$；\n- 设 $d_i=\\mathrm{dist}(p_i,p_{i+1})(1\\leq i\\leq n-1)$，那么你给出的排列需要满足以上条件的前提下，最小化 $\\oplus_{i = 1} ^ {n - 1}d_i$，其中 $\\oplus$ 表示按位异或。\n\n如果有多种满足条件的排列，输出任意一种均可。\n\n## Input\n\n从标准输入读入数据。\n\n本题有多组测试数据。第一行输入一个正整数 $T$ 表示测试数据组数。\n\n对于每组数据，第一行输入三个正整数 $n,s,t$，接下来 $n-1$ 行每行两个正整数 $u,v$，表示地点 $u$ 和 $v$ 有直接无向道路连接（即树上的一条边）。\n\n## Output\n\n输出到标准输出。\n\n对于每组数据，输出一行 $n$ 个正整数 $p_1,p_2,\\cdots,p_n$，你需要保证其为 $1$ 到 $n$ 的一个排列且 $p_1=s$，$p_n=t$，且 $\\oplus_{i = 1} ^ {n - 1} d_i$ 最小。\n\n[samples]\n\n## Background\n\n[原题面存档。](https://www.luogu.com.cn/paste/pd4a89g5)\n\n## Note\n\n**样例 1 解释**\n\n该样例共有三组测试数据。\n\n- 对于第一组数据，$\\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $0$，样例输出为 $1,2,3$，其中 $d_1=d_2=1$。\n- 对于第二组数据，$\\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $2$，样例输出为 $3,2,1,4$，其中 $d_1=d_2=1$，$d_3=2$；另一种合法输出为 $3,1,2,4$。\n- 对于第三组数据，$\\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$。\n\n**样例 2 解释**\n\n值得注意的是，该输入数据由所有满足 $n\\leq 10$ 的，且所有不同 $s$ 和 $t$ 的相对位置的可能的树形态构成。\n\n这个样例，无疑是善良的出题人无私的馈赠。中间忘了。出题人相信，这个美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。\n\n### 数据范围\n\n设 $\\sum n$ 表示单个测试点内所有数据的 $n$ 的和。对于所有测试数据，\n\n- $T≥1$；\n- $2\\leq n\\leq 5\\times 10 ^4$，$\\sum n\\leq 5\\times 10 ^ 5$；\n- $1\\leq s,t\\leq n$，$s\\neq t$；\n- $1\\le u,v\\le n$，$u\\neq v$；\n- 输入的 $n-1$ 个 $(u,v)$ 构成一棵树。\n\n| 子任务编号 | $n$                   | $\\sum n$              | 特殊性质 | 分数 |\n|-------|-----------------------|-----------------------|------|----|\n| 1     | $\\le 8$               | $\\le 10^{3}$          | 无    | 5  |\n| 2     | $\\le 12$              | $\\le 10^{3}$          | 无    | 8  |\n| 3     | $\\le 5 \\times 10^{4}$ | $\\le 5 \\times 10^{5}$ | A    | 17 |\n| 4     | $\\le 5 \\times 10^{4}$ | $\\le 5 \\times 10^{5}$ | B    | 20 |\n| 5     | $\\le 5 \\times 10^{4}$ | $\\le 5 \\times 10^{5}$ | C    | 17 |\n| 6     | $\\le 10^{3}$          | $\\le 10^{4}$          | D    | 10 |\n| 7     | $\\le 5 \\times 10^{4}$ | $\\le 5 \\times 10^{5}$ | 无    | 23 |\n\n特殊性质 A：保证每个点度数小于等于 $2$。\n\n特殊性质 B：保证对于任意 $x$ 有 $\\mathrm{dist}(s,x)+\\mathrm{dist}(x,t)\\le \\mathrm{dist}(s,t)+2$。\n\n特殊性质 C：保证 $\\mathrm{dist}(s,t)=1$。\n\n特殊性质 D：该子任务共有五个测试点，对于每一个测试点，保证 $T=10$ 且 $n=1000$，并且每个测试数据中，$s$ 在 $1\\sim n$ 中等概率随机生成，$t$ 从 $1\\sim n$ 除去 $s$ 中等概率随机生成，树从所有 $n$ 个点的有标号树中等概率随机生成。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10212","tags":["2024","Special Judge","CTSC/CTS"],"sample_group":[["3\n3 1 3\n1 2\n2 3\n4 3 4\n1 2\n2 3\n2 4\n5 1 2\n1 2\n1 3\n2 4\n3 5\n","1 2 3\n3 2 1 4\n1 5 3 4 2"],["见题目目录下的 2.in 与 2.ans。",""]],"created_at":"2026-03-03 11:09:25"}}