CTREE - Tô màu nhỏ nhất
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 10010
#define MAXV 20
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
vector<int> g[MAX];
int f[MAX][MAXV+7];
int p[MAX],r[MAX];
int n;
void loadtree(void) {
scanf("%d",&n);
REP(zz,n-1) {
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
}
void dfs(int u) {
FOR(i,1,MAXV) f[u][i]=i;
FORE(it,g[u]) if (*it!=p[u]) {
int v=*it;
p[v]=u;
dfs(v);
FOR(i,1,MAXV) {
int t=-1;
FOR(j,1,MAXV) if (i!=j && (t<0 || f[v][t]>f[v][j])) t=j;
f[u][i]+=f[v][t];
}
}
}
void trace(int u,int c) {
r[u]=c;
FORE(it,g[u]) if (*it!=p[u]) {
int v=*it;
int t=-1;
FOR(i,1,MAXV) if (i!=c && (t<0 || f[v][t]>f[v][i])) t=i;
trace(v,t);
}
}
void process(void) {
dfs(1);
int j=1;
FOR(i,1,MAXV) if (f[1][j]>f[1][i]) j=i;
trace(1,j);
printf("%d\n",f[1][j]);
FOR(i,1,n) printf("%d\n",r[i]);
}
int main(void) {
loadtree();
process();
return 0;
}