题解：P17660 [IO 2025 #3] 噩梦迷宫

Naoero · 2026-10-21 19:20:29 · 题解

题目大意

给定一棵 n 个节点的树，构造从任意节点出发，恰好访问每个节点一次后回到起点，且相邻两次访问的节点在树上的距离不超过 3 的路线。

思路

首先规定好根节点 1，深度为 0，然后我们想的是如何往下跳才能做到跳完这些子树的同时还能跳回来，且每个节点不能走两次，那是不是可以隔着一个格子跳这样来回就都可以走得通，于是我们想到了讨论对于当前深度的奇偶性，可以对其进行分析：

从根开始往下走，操作一下样例于是讨论出：

• 偶数深度的节点进入时输出。
• 奇数深度的节点回溯时输出。

最后再输出 1，形成回路。

正确性

每个节点只在进入或回溯时输出一次，且回到根的时候可以合法地切换到下一个子树，这样肯定不会重复或遗漏。

那么对于以 u 为根的非叶子子树：

• 若 u 深度为偶数，输出序列以 u 开始，以某个孩子结束。
• 若 u 深度为奇数，输出序列以某个孩子开始，以 u 结束。

叶子子树的首尾都是自身。因此，父节点与孩子子树的衔接距离至多为 2；相邻孩子子树之间的衔接距离至多为 3。

整个序列以根开始，以根的某个孩子结束，最后刚好可以再返回根，故构造正确。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
vector<int> g[200010];
vector<int> ans;
int d[200010];
void dfs(int u,int f,int d){
    if(d%2==0) ans.push_back(u);
    for(int v:g[u]) if(v!=f) dfs(v,u,d+1);
    if(d%2==1) ans.push_back(u);
}
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0,0);
    for(int i=0;i<n;i++) cout<<ans[i]<<' ';
    cout<<1<<endl;
    return 0;
}

时间和空间复杂度均为 O(n)。