题意

题目链接

有一棵树有粉点有黑点，从根开始走，每走到一个点都会改变颜色。求一种方案使所有点变成黑色。

解析

我们考虑使用递归的方式寻找答案。假设一棵树的深度只有 $2$，那么我们只需要从根开始，找到粉点，走过去再回来，重复几次，就可以使下一层的所有点变为黑色。

以这种方式一层一层染色，最后对于根节点，如果为黑色不用处理，否则，走下去，走回来，再走下去然后停止就可以了（题目不要求一定在树根结束）。

详见代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct edge{
    int to,nxt;
}e[N<<1];
int head[N],cnt,col[N],tot,step[N<<5],n;//step要开大点！ 
inline void add(int u,int v){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
inline void change(int u){
    col[u]=-col[u];
}
inline void dfs(int u,int fa){
    bool yezi=true;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        yezi=false;
    }
    if(!yezi){//走到 u
        step[++tot]=u;
        change(u);
    }
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        if(col[v]==-1){//处理儿子中的粉点
            step[++tot]=v;
            step[++tot]=u;
            change(v);change(u);
        }
    }
    if(!yezi&&fa!=0){//走回到父亲
        step[++tot]=fa;
        change(fa);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&col[i]);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    change(1);
    dfs(1,0);
    if(col[1]==-1){
        int i=head[1];
        int v=e[i].to;
        step[++tot]=v;
        step[++tot]=1;
        step[++tot]=v;
    }
    for(int i=1;i<=tot;i++)
        printf("%d ",step[i]);
    return 0;
}