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

_hxy_ · 2026-10-20 15:32:59 · 题解

思路解析：

观察这幅图，发现按照深度奇偶来分黑白，每次都跳到距离为 2 的点上，做完了。每次先把黑点加入答案，再递归，最后再把白色点加入。

代码展示：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define For(i,l,r) for(int i=l,END##i=r;i<=END##i;++i)
#define Rof(i,l,r) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
const int MOD=1e9+7;
const int N=2e5+10;

int a[N],n,vis[N],ans[N],dis[N],len;
vector<int> g[N];

inline void dfs(int x){
    for(auto e:g[x]) if(vis[e]==-1){//不能重复走
        vis[e]=vis[x]^1;//染色
        dfs(e);
    }
    return;
}

inline void dfs1(int x){
    if(vis[x]) ans[++len]=x;//黑点
    for(auto e:g[x]) if(dis[e]==-1)
        dis[e]=0,dfs1(e);//标记，递归
    if(!vis[x]) ans[++len]=x;//白点
    return;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n;
    For(i,1,n-1){
        vis[i]=vis[i+1]=dis[i]=dis[i+1]=-1;//初始化
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);//建立
        g[v].push_back(u);
    }
    vis[1]=1;
    dfs(1);//染色，1表示黑点，0辨识白点
    dis[1]=1;
    dfs1(1);
    ans[++len]=1;//要回到1
    For(i,1,len) cout<<ans[i]<<' ';
    return 0;
}