Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals

C题思路：生成树上的dfs，完全没见过，留作复习

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<string>
#include<vector>
#define maxn 210000
using namespace std;
int n;
vector<int>aaa[maxn];
int power[maxn];
int color[maxn];


void dfs(int x, int fa) {	//对第x个节点的子节点们开始染色，x的父节点是fA
	int c = 1;
	for (int i = 0; i < aaa[x].size(); i++) {
		int temp = aaa[x][i];
		if (color[temp] != 0)continue;
		while (c == color[x] || c == color[fa])c++;
		color[temp] = c;
		dfs(temp, x);
		c++;
	}
}


int ans;
int main() {
	memset(color, 0, sizeof(color));
	memset(power, 0, sizeof(power));
	ans = 0;
	scanf("%d", &n);
	int a, b;
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &a, &b);
		power[a]++; power[b]++;
		ans = max(ans, max(power[a], power[b]));


		aaa[a].push_back(b);
		aaa[b].push_back(a);
	}
	ans++;
	cout << ans << endl;
	dfs(1, 0);
	for (int i = 1; i <= n; i++) {
		if (i != 1)printf(" ");
		printf("%d", color[i]);
	}
	printf("
");
}