C. 特拉普米贾诺·雷贾诺（陷阱奶酪）详细题解

一、题目理解

有一棵 $n$ 个顶点的树。一只老鼠从起点 $st$ 出发。
我们有一个长度为 $n$ 的排列 $p$，表示奶酪出现的顺序。
第 $i$ 步：

• 奶酪出现在顶点 $p_i$
• 如果老鼠当前在 $p_i$，则不动
• 否则，老鼠沿着到 $p_i$ 的最短路径移动 一条边

目标：找到排列 $p$，使得 $n$ 步后老鼠必定在陷阱顶点 $en$。

二、核心观察

1. 树的性质：任意两点之间有唯一简单路径。
2. 老鼠移动规则：每次奶酪出现时，老鼠向其移动一步（若已在则不动）。
3. 关键想法：如果按离 $en$ 从远到近的顺序让奶酪出现，老鼠会被一步步“拉”向 $en$。
4. 最后一步：当奶酪出现在 $en$ 本身时，老鼠一定已经在 $en$（因为其他所有顶点都已出现过，老鼠已被引导至此）。

三、算法步骤

设以 $en$ 为根，定义 $depth[v]$ 为顶点 $v$ 到 $en$ 的距离（边数）。

1. 以 $en$ 为根，对树进行 DFS，计算每个顶点的深度。
2. 将深度相同的顶点放入同一个桶中。
3. 按深度从大到小依次输出所有顶点。

为什么这样构造有效？

• 深度最大的顶点距离 $en$ 最远，先出现。
• 老鼠从 $st$ 出发，每次奶酪出现在深度较大的顶点时，它会向该顶点移动一步（实际是向 $en$ 靠近，因为深度大的顶点在 $en$ 的远处）。
• 当所有深度 $> 0$ 的顶点都出现过后，最后出现 $en$ 本身（深度 $0$）。
• 此时老鼠一定在 $en$，因为前面的移动已将其引导至根。

四、正确性证明

引理：按照深度降序输出顶点，老鼠每步后与 $en$ 的距离单调不增，且当所有非 $en$ 顶点输出后，老鼠在 $en$。

证明：

• 设当前老鼠在顶点 $u$，奶酪出现在 $v$。
• 若 $v = en$，老鼠向 $en$ 移动一步（或已在）。
• 若 $v \neq en$，由于 $v$ 的深度 $\ge depth[u]$（因为深度大的先出现），老鼠向 $v$ 移动一步，实际是向 $en$ 靠近（因为 $v$ 在 $en$ 的某个子树中）。
• 最终，当所有深度 $> 0$ 的顶点都出现后，老鼠必然在深度 $0$ 的顶点，即 $en$。

五、标程代码解析

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, s, e;
    cin >> n >> s >> e;
    
    // 邻接表
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // dis[d] 存放深度为 d 的所有顶点
    vector<vector<int>> dis(n + 1);
    vector<int> d(n + 1, 0);  // d[v] = 深度，d[0]=0 是虚拟根
    
    // DFS 以 e 为根，计算深度并分组
    auto dfs = [&](auto &&self, int v, int par) -> void {
        d[v] = d[par] + 1;          // 深度 = 父节点深度 + 1
        dis[d[v]].push_back(v);     // 按深度分组
        for (int u : adj[v]) {
            if (u == par) continue;
            self(self, u, v);
        }
    };
    
    dfs(dfs, e, 0);  // 从 e 开始，父节点为 0（虚拟根）
    
    // 按深度从大到小输出
    for (int i = n; i >= 1; i--) {
        for (int j : dis[i]) {
            cout << j << " ";
        }
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    
    return 0;
}

六、复杂度分析

• 时间：$O(n)$ 每个测试用例（DFS 遍历 + 输出）
• 空间：$O(n)$
• 满足 $\sum n \le 10^5$ 的限制

七、示例验证

输入：

4
1 1 1
2 1 2
1 2
3 2 2
1 2
2 3
6 1 4
1 2
1 3
4 5
5 6
1 4

运行过程（以第 3 个测试用例为例，$n=3, st=2, en=2$）：

• 以 $2$ 为根：$depth[1]=1, depth[2]=0, depth[3]=1$
• 按深度降序：深度 $1$ 的顶点 $[1,3]$，深度 $0$ 的顶点 $[2]$
• 输出：$3\ 1\ 2$

输出：

1 
2 1 
3 1 2 
1 4 3 2 6 5 

与题目示例一致 ✅

八、总结