原题传送门
本题的难点主要是在定义递归结束后某个节点的状态。定义 \text{dfs(x)} 表示在递归完以 \text{x} 为根的子树把这个子树染黑后，停下来的点？显然非常不可做。
考虑定义 \text{dfs(x)} 表示从 \text{x} 开始走，最后回到 \text{x} ，将以 \text{x} 为根的子树中除了 \text{x} 以外的节点都变成黑色（\text{x} 的颜色可以任意）。
这样确定了递归后我们在什么位置，题目经过这样的转化变得可做起来。
这个 \text{x} 的颜色之后会由父亲处理。
那么如何dfs，或者说dfs的流程是怎样的呢？
这样做一遍后，除了根节点以外都是黑色，然后如果根是白色，找一个儿子（一定是黑色），过去-回来-过去然后结束路径即可。
容易证明这样构造的路径长度是可以接受的，大概是常数乘上 $\text{n}$ 。
时间复杂度 $\text{O(n)}$ ， $\text{dfs}$ 时输出路径即可。
感觉思路已经说得非常清晰了，实现基本就是翻译一下。读者可以锻炼一下自己的码力。建议大家不看以下代码自己写出来。
## Code
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
const int N=2e5+10;
int n,fir[N],tot,col[N],fa[N];
struct node {int to,nex;} e[N << 1];
void add(int u,int v)
{
e[++tot].to=v;
e[tot].nex=fir[u];
fir[u]=tot;
return ;
}
void init(int x,int dad)
{
fa[x]=dad;
for(int i=fir[x];i;i=e[i].nex)
if(e[i].to^dad) init(e[i].to,x);
return ;
}
void dfs(int x)
{
printf("%d ",x);
for(int i=fir[x];i;i=e[i].nex)
if(e[i].to^fa[x])
{
col[e[i].to]^=1;//往子树走
dfs(e[i].to);
printf("%d ",x);
col[x]^=1;//回来
if(!col[e[i].to])//处理儿子颜色
{
printf("%d %d ",e[i].to,x);
col[e[i].to]=1;
col[x]^=1;
}
}
return ;
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) {scanf("%d",&col[i]); if(col[i] < 0) col[i]=0;}
for(int i=1,u,v;i<n;i++) {scanf("%d%d",&u,&v); add(u,v); add(v,u);}
init(1,0); dfs(1);
if(!col[1]) printf("%d 1 %d ",e[fir[1]].to,e[fir[1]].to);//最后的白点
// fclose(stdin); fclose(stdout);
return 0;
}
```
难度建议蓝。
感谢阅读！您的评论和点赞是对作者最大的支持！