Codeforces 763A

乍看之下感觉有点无从下手，，其实是个很简单的水题，陷入僵局

题目大意：给一棵树，树上每个节点都染色，问能否取下一个节点，使得剩余所有子树上的点的颜色都相同。能输出YES和取下的节点编号，否则输出NO。

解题思路：感觉无从下手，结果xjb找找情况画画图脑补个策略就行了——

　　随便从一个点开始进行搜索，如果和它颜色不同的相邻节点个数（除去父节点）大于等于2，那答案肯定是它没跑了，如果在这之前已经确定下了一个答案并且这个答案不是自己，咖喱给给。

　　如果和它颜色不同的相邻节点个数（除去父节点）为1，那么令答案为该相邻节点。同样如果已经确定答案但是答案不是自己，gg。

　　随便测了几组数据没问题就交了过了。

　　如果全部节点都是一个颜色，则出现flag为1而res尚未被赋值，特判输出之。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long ll;

#define sqr(x) ((x)*(x))

const int N=2e5+;

int head[N],to[N<<],nxt[N<<],cnt;

int n,c[N],res,flag;

void init(){

    memset(head,-,sizeof(head));

    cnt=res=;

    flag=;

}

void addEdge(int u,int v){

    nxt[cnt]=head[u];

    to[cnt]=v;

    head[u]=cnt++;

}

void dfs(int u,int pre){

    if(!flag) return;

    int tot=,id;

    for(int i=head[u];~i;i=nxt[i]){

        int v=to[i];

        if(v==pre) continue;

        if(c[u]!=c[v]){

            tot++;

            id=v;

        }

    }

    if(tot>){

        if(tot==){

            if(res){

                if(res!=u) flag=;

            }

            else res=id;

        }

        else{

            if(res&&res!=u) flag=;

            else res=u;

        }

    }

    for(int i=head[u];~i;i=nxt[i]){

        int v=to[i];

        if(v==pre) continue;

        dfs(v,u);

    }

}

int main(){

    //freopen("in.txt","r",stdin);

    while(~scanf("%d",&n)){

        init();

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

            int u,v;

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

            addEdge(u,v),addEdge(v,u);

        }

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

            scanf("%d",c+i);

        dfs(,);

        if(flag) printf("YES\n%d\n",res?res:);

        else puts("NO");

    }

    return ;

}

巴特西

Codeforces 763A

最新文章

热门文章