「CodeForces - 717E」Paint it really, really dark gray （dfs）

BUPT 2017 summer training (for 16) #1H

题意

每个节点是黑色or白色，经过一个节点就会改变它的颜色，一开始在1节点。求一条路径使得所有点变成黑色。

题解

dfs时每个节点的孩子处理完，这时候如果颜色是白色，那么再去一下父亲节点再回来，就变成黑色了。

如果是1号点，那就去它的孩子节点，再回来，再去它孩子节点。

代码

#include <cstdio>

#define N 200005

struct edge{

    int to,next;

}e[N<<1];

int head[N],cnt;

int n,a[N];

void add(int u,int v){

    e[++cnt]=(edge){v,head[u]};

    head[u]=cnt;

}

int ans[N<<1],top;

void dfs(int x,int fa){

    ans[++top]=x;

    a[x]*=-1;

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa)continue;

        dfs(v,x);

        ans[++top]=x;

        a[x]*=-1;

    }

    if(a[x]==-1){

        if(x!=1){

            ans[++top]=fa;

            a[fa]*=-1;

            ans[++top]=x;

            a[x]=1;

        }else{

            ans[++top]=e[head[1]].to;

            ans[++top]=1;

            ans[++top]=e[head[1]].to;

        }

    }

}

int main(){

    scanf("%d",&n);

    bool ex=0;

    for(int i=1;i<=n;++i){

        scanf("%d",&a[i]);

        if(a[i]==-1)

            ex=1;

    }

    for(int i=1,u,v;i<n;++i){

        scanf("%d%d",&u,&v);

        add(u,v);add(v,u);

    }

    if(!ex)printf("1");

    else{

        a[1]*=-1;

        dfs(1,0);

        for(int i=1;i<=top;++i)

            printf("%d ",ans[i]);

    }

    return 0;

}

巴特西

「CodeForces - 717E」Paint it really, really dark gray （dfs）

题意

题解

代码

最新文章

热门文章