题意分析
记起点为 $s$，终点为 $t$。
原树没有根，考虑人为设定一个根。不妨以 $t$ 为根节点。
那么求排列等价于求一种移动顺序，使得老鼠最后停留在根节点。
移动可以分两种：向上和向下。显然向上是更优的。
设老鼠当前位于节点 $p$，如果在 $x$ 处生成一个奶酪：
- 若 $x$ 是 $p$ 的祖先节点，则这是优的。
- 若 $x$ 是 $p$ 的子树内节点，则这是劣的。
- 否则 $x$ 仍然是优的，因为 $p$ 会走向 $\operatorname{lca}(x,p)$，会向上。
考虑先将子树内的走完，因此可以贪心：先走深度大的节点。
DFS 一遍，按照深度分类后从大到小输出即可。（BFS 也许可以更好求解，但是没必要。）
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5;
int n,s,t,depth[N+1];
vector<int>g[N+1],node[N+1];
void dfs(int x,int fx){
depth[x]=depth[fx]+1;
node[depth[x]].push_back(x);
for(int i:g[x]){
if(i==fx){
continue;
}
dfs(i,x);
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
for(int i=1;i<=n;i++){
g[i].resize(0);
node[i].resize(0);
}
cin>>n>>s>>t;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(t,0);
for(int i=n;i>=1;i--){
for(int j:node[i]){
cout<<j<<' ';
}
}
cout<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
