http://codeforces.com/contest/782/problem/C
题意：给一棵树染最少的颜色，使得相邻距离为2的点都是不同的颜色，问最少是多少种颜色并输出每个点的颜色。
思路：比赛的时候没想到是找度最大的一个点并+1就是总颜色数，一直想怎么构造。
最后的总颜色数是度最大的一个点的度数+1。因为我们选的这个点到儿子的距离为1，因此其某一个儿子到另一个儿子的距离为2，就是这些儿子都要染成不同的颜色，+1是因为自己本身也要是不同的颜色。
然后确定了总颜色数，就可以DFS染色了。
参数记录一个上上个结点和上个结点染了什么颜色，只要儿子染成不同的就可以了，注意儿子之间颜色也要不同。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 200010 4 struct Edge { 5 int v, nxt; 6 } edge[N*2]; 7 int head[N], tot, col[N], deg[N], ans; 8 9 void Add(int u, int v) { 10 edge[tot] = (Edge) {v, head[u]}; head[u] = tot++; 11 edge[tot] = (Edge) {u, head[v]}; head[v] = tot++; 12 } 13 14 void dfs(int u, int fa, int c1, int c2) { 15 int c = 1; 16 for(int i = head[u]; ~i; i = edge[i].nxt) { 17 int v = edge[i].v; 18 if(v == fa) continue; 19 if(col[v]) continue; 20 for( ; c <= ans; c++) 21 if(c != c1 && c != c2) { 22 col[v] = c; break; 23 } 24 c++; 25 dfs(v, u, col[v], col[u]); 26 } 27 } 28 29 int main() { 30 int n; 31 scanf("%d", &n); 32 memset(head, -1, sizeof(head)); 33 for(int i = 1; i < n; i++) { 34 int u, v; 35 scanf("%d%d", &u, &v); 36 deg[u]++; deg[v]++; 37 Add(u, v); 38 } 39 ans = 0; 40 for(int i = 1; i <= n; i++) if(ans < deg[i] + 1) ans = deg[i] + 1; 41 42 col[1] = 1; 43 dfs(1, -1, 1, -1); 44 printf("%d ", ans); 45 for(int i = 1; i <= n; i++) printf("%d ", col[i]); 46 return 0; 47 }