AC日记——Andryusha and Colored Balloons codeforces 780c

C - Andryusha and Colored Balloons

思路：

　　水题；

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define maxn 200005

int n,head[maxn],cnt,E[maxn<<1],V[maxn<<1],dis[maxn],ans;

void dfs(int now,int fa)
{
    int ki=0;
    for(int i=head[now];i;i=E[i])
    {
        if(V[i]==fa) continue;
        ki++;
        if(ki==dis[fa]) ki++;
        if(ki==dis[now]) ki++;
        if(ki==dis[fa]) ki++;
        if(ki==dis[now]) ki++;
        dis[V[i]]=ki,dfs(V[i],now);
    }
}

int main()
{
    scanf("%d",&n);int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
        E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
    }
    dis[1]=1,dfs(1,0);
    for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
    printf("%d
",ans);
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}