CTREE - Tô màu nhỏ nhất
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111111
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
int n,f[maxn][4],x[maxn],cha[maxn],u,v,KQ,t;
VVI T;
//VVI::iterator it;
void DFS(int u){
int v;
for(int i = 1;i<=3;i++) f[u][i] = i;
TR(T[u],it)
if((v=*it)!=cha[u]){
cha[v] = u;
DFS(v);
f[u][1] += f[v][2] <? f[v][3];
f[u][2] += f[v][1] <? f[v][3];
f[u][3] += f[v][1] <? f[v][2];
}
//printf("%d %d %d %d\n",u,f[u][1],f[u][2],f[u][3]);
}
void tim(int u,int gt){
x[u] = gt;
int kq,v,gtv;
TR(T[u],it){
if((v=*it)!=cha[u]){
kq = oo;
for(int i = 1;i<=3;i++) if(i!=gt && f[v][i]<kq){
kq = f[v][i];
gtv = i;
}
tim(v,gtv);
}
}
}
int main(){
//freopen("CTREE.in","r",stdin);
scanf("%d",&n);
T.resize(n+2);
for(int i = 1;i<n;i++){
scanf("%d %d",&u,&v);
T[u].push_back(v);
T[v].push_back(u);
}
DFS(1);
KQ = oo;
for(int i = 1;i<=3;i++) if(f[1][i]<KQ){ KQ = f[1][i],t = i;}
tim(1,t);
printf("%d\n",KQ);
for(int i = 1;i<=n;i++) printf("%d\n",x[i]);
// getch();
}