cf提交链接

$Code$

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;
constexpr int M = 2 * N;

int n; // 点数
int he[N], ed[M], ne[M], idx; // 数组模拟邻接链表
int c[N]; // c[i]表示i点的颜色
int color_num; // 总共用了多少种颜色
int root = -1; // 根节点的编号
int used[N]; // uese[i]表示已经用过i去更新它所连接的点的颜色了

void add(int a, int b) {
	ed[idx] = b, ne[idx] = he[a], he[a] = idx ++;
}

int main() {
	
	memset(he, -1, sizeof he);
	
	cin >> n;
	
	// 建图
	for (int i = 1; i <= n - 1; i ++) {
		int a, b; cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	
	/*
	  根据贪心可得：
	  “连接最多的其他节点”的点，所连接的点的数量+1就是
	  颜色的种类。
	  那么这个“连接最多的其他节点”的点，就可以定义为
	  根节点。
	 */
	for (int i = 1; i <= n; i ++) {
		int num = 1; // i点所连接的点的数量
		for (int j = he[i]; j != -1; j = ne[j]) {
			num ++;
		}
		if (num > color_num) {
			color_num = num;
			root = i;
		}
	}
	
	c[root] =  1; // 根节点的颜色是1号
	queue <int> q;
	for (int i = he[root], k = 2; i != -1; i = ne[i], k ++) {
		c[ed[i]] = k;
		q.emplace(ed[i]);
		// 根节点所连接的点依次的颜色为2、3、4...color_num
	}
	
	// 输出颜色数
	cout << color_num << endl;
	
	while (!q.empty()) {
		// 用已经涂色的t点更新它所连接的点的颜色
		int t = q.front(); q.pop();
		// 遍历t连接的点
		for (int i = he[t]; i != -1; i = ne[i]) {
			int j = ed[i]; // 连接的点是j
			if (c[j] == 0) { // 如果j还没涂色
				// 遍历所有颜色
				for (int cr = 1; cr <= color_num; cr ++) {
					int ok = 1;
					for (int k = he[j]; k != -1 && ok; k = ne[k]) {
						if (c[ed[k]] == cr) {
							ok = 0;
						}
						for (int m = he[ed[k]]; m != -1 && ok; m = ne[m]) {
							if (c[ed[m]] == cr) {
								ok = 0;
							}
						}
					}
					/*
					  如果j点所连接的点 和 j点所连接的点连接的点
					  都没有用这种颜色cr，那么j点的颜色就涂为cr
					 */
					if (ok) {
						c[j] = cr;
						q.emplace(j); // 用j点更新其他点的颜色
						break;
					}
				}
			}
		}
	}
	
	// 输出各个点的颜色
	for (int i = 1; i <= n; i ++) {
		cout << c[i] << ' ';
	}
	cout << endl;
	return 0;
}