Codeforces Round #403 div2 C. Andryusha and Colored Balloons

题目链接：Codeforces Round #403 div2 C. Andryusha and Colored Balloons

题意：

给你一棵n个节点的树，然后让你染色，规定相连的三个 节点不能同色，问需要的最少颜色，并输出其中一种方案。

题解：

因为只有相邻3个节点不同色。

所以直接DFS，每个节点都从1开始。

然后ans[v]!=ans[u]!=ans[fa]就行。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

const int N=2e5+7;
int n,g[N],v[N*2],nxt[N*2],ed,cnt,ans[N];
void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}

void dfs(int x,int fa)
{
    int cnt=1;
    for(int i=g[x];i;i=nxt[i])if(v[i]!=fa)
    {
        while(cnt==ans[fa]||cnt==ans[x])cnt++;
        ans[v[i]]=cnt,cnt++;
    }
    for(int i=g[x];i;i=nxt[i])if(v[i]!=fa)
    {
        dfs(v[i],x);
    }
}

int main(){
    scanf("%d",&n);
    int x,y;
    F(i,1,n-1)
    {
        scanf("%d%d",&x,&y);
        adg(x,y),adg(y,x);
    }
    ans[1]=1;
    dfs(1,0);
    int an=0;
    F(i,1,n)an=max(an,ans[i]);
    printf("%d
",an);
    F(i,1,n)printf("%d%c",ans[i]," 
"[i==n]);
    return 0;
}