CTREE - Tô màu nhỏ nhất
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 10004;
const int oo = trunc(1e9);
using namespace std;
int F[N][4], color[N], n;
vector<int> a[N], child[N];
bool visit[N];
void DFS(int u) {
visit[u] = true;
for(int i=0; i<a[u].size(); i++) {
int v = a[u][i];
if (!visit[v]) {
child[u].push_back(v);
DFS(v);
}
}
}
int Min(int i, int c) {
int mi = oo;
for(int j=1; j<=3; j++)
if (j != c) mi = min(mi, F[i][j]);
return mi;
}
void DP(int u) {
if (child[u].size() == 0) {
for(int i=1; i<=3; i++)
F[u][i] = i;
return;
}
for(int i=0; i<child[u].size(); i++) {
int v = child[u][i];
DP(v);
}
for(int i=1; i<=3; i++) {
F[u][i] = i;
for(int j=0; j<child[u].size(); j++) {
int v = child[u][j];
F[u][i] += Min(v, i);
}
}
}
void Play(int u, int c) {
color[u] = c;
for(int i=0; i<child[u].size(); i++) {
int v = child[u][i];
int mi = oo, next;
for(int j=1; j<=3; j++)
if (j != c && F[v][j] < mi) {
mi = F[v][j]; next = j;
}
Play(v, next);
}
}
int main()
{
//freopen("CTREE.inp", "r", stdin);
scanf("%d\n", &n); int u, v;
for(int i=1; i<n; i++) {
scanf("%d %d\n", &u, &v);
a[u].push_back(v);
a[v].push_back(u);
}
DFS(1);
DP(1);
int root = 1;
if (F[1][2] < F[1][root]) root = 2;
if (F[1][3] < F[1][root]) root = 3;
Play(1, root);
printf("%d\n", F[1][root]);
for(int i=1; i<=n; i++) printf("%d\n", color[i]);
return 0;
}