CF717E Paint it really, really dark gray 题解

发布于 2021-02-05  1.73k 次阅读


题意

题目链接

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

解析

我们考虑使用递归的方式寻找答案。假设一棵树的深度只有 $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;
}

月流华 岁遗沙 万古吴钩出玉匣