Codeforces 781A：Andryusha and Colored Balloons（DFS染色）

http://codeforces.com/contest/782/problem/C

题意：给一棵树染最少的颜色，使得相邻距离为2的点都是不同的颜色，问最少是多少种颜色并输出每个点的颜色。

思路：比赛的时候没想到是找度最大的一个点并+1就是总颜色数，一直想怎么构造。

最后的总颜色数是度最大的一个点的度数+1。因为我们选的这个点到儿子的距离为1，因此其某一个儿子到另一个儿子的距离为2，就是这些儿子都要染成不同的颜色，+1是因为自己本身也要是不同的颜色。

然后确定了总颜色数，就可以DFS染色了。

参数记录一个上上个结点和上个结点染了什么颜色，只要儿子染成不同的就可以了，注意儿子之间颜色也要不同。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 200010

 struct Edge {

     int v, nxt;

 } edge[N*];

 int head[N], tot, col[N], deg[N], ans;

 void Add(int u, int v) {

     edge[tot] = (Edge) {v, head[u]}; head[u] = tot++;

     edge[tot] = (Edge) {u, head[v]}; head[v] = tot++;

 }

 void dfs(int u, int fa, int c1, int c2) {

     int c = ;

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

         int v = edge[i].v;

         if(v == fa) continue;

         if(col[v]) continue;

         for( ; c <= ans; c++)

             if(c != c1 && c != c2) {

                 col[v] = c; break;

             }

         c++;

         dfs(v, u, col[v], col[u]);

     }

 }

 int main() {

     int n;

     scanf("%d", &n);

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

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

         int u, v;

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

         deg[u]++; deg[v]++;

         Add(u, v);

     }

     ans = ;

     for(int i = ; i <= n; i++) if(ans < deg[i] + ) ans = deg[i] + ;

     col[] = ;

     dfs(, -, , -);

     printf("%d\n", ans);

     for(int i = ; i <= n; i++) printf("%d ", col[i]);

     return ;

 }