ZR 路径（构造方案）

满分做法：

对于一条链的情况，我们可以隔一个走一个，最后再走回来，如下：

那对于树来说，我们可以直接扩展：如 果当前节点深度是奇数，那么我们在 DFS 前输出这个点，否则在 DFS 完所有孩子之 后再输出这个点。自己手画一下，感觉很对！！！

#include<cstring>
#include<queue>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int maxm=6e5+7;
int n;
int pre[maxm],last[maxm],other[maxm],l;
int dep[maxm];
void add(int x,int y)
{
 l++;
 pre[l]=last[x];    
 last[x]=l;
 other[l]=y;
}
void dfs(int x,int fa)
{
  if(dep[x]%2==1)
  printf("%d ",x);
  for(int p=last[x];p;p=pre[p])
  {
   int v=other[p];
   if(v==fa) continue;
   dep[v]=dep[x]+1;
   dfs(v,x);
  }
  if(dep[x]%2==0)
  printf("%d ",x);
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n-1;i++)
 {
  int x,y;
  scanf("%d%d",&x,&y);
  add(x,y);
  add(y,x);
 }
 dep[1]=1;
 printf("Yes
");
 dfs(1,0);
 return 0;    
}
/*
8
1 2
2 3
3 4
4 5
4 6
4 7
7 8
*/