CTREE - Tô màu nhỏ nhất
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include "stdio.h"
#include "iostream"
#include "vector"
using namespace std;
#define maxc 30
int n;
vector<vector<int> > ke;
int f[10001][maxc+1];
int father[10001], la[10001];
void nhap() {
int u,v;
scanf("%d",&n);
ke.resize(n+1);
for(int i=1;i<n;++i) {
scanf("%d%d",&u,&v);
ke[u].push_back(v);
ke[v].push_back(u);
}
}
void dfs(int i) {
for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p)
if(*p!=father[i]) {
father[*p]=i;
dfs(*p);
}
for(int k=1;k<=maxc;++k) {
f[i][k]=k;
for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p) if(*p!=father[i]) {
int fmin=1000000000;
for(int t=1;t<=maxc;++t) if(t!=k) fmin<?=f[*p][t];
f[i][k]+=fmin;
}
}
}
void truyvet(int i,int k) {
la[i]=k;
for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p) if(*p!=father[i]) {
int fmin=1000000000,tmin=-1;
for(int t=1;t<=maxc;++t) if(t!=k && fmin>f[*p][t]) {
fmin=f[*p][t];
tmin=t;
}
truyvet(*p,tmin);
}
}
void xuly() {
dfs(1);
int fmin=1000000000,kmin=-1;
for(int k=1;k<=maxc;++k) {
if(f[1][k]<fmin) {
fmin=f[1][k];
kmin=k;
}
}
truyvet(1,kmin);
printf("%d\n",f[1][kmin]);
for(int i=1;i<=n;++i) printf("%d\n",la[i]);
}
int main() {
nhap();
xuly();
return 0;
}