CTREE - Tô màu nhỏ nhất
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=10001;
type ar=array[0..maxn] of longint;
var n,dem:longint;
b:array[1..maxn,0..1] of longint;
f:array[1..3,1..maxn] of longint;
sl,pos,cur,re,d:ar;
a:array[1..maxn*2] of longint;
procedure rf;
var i,j:longint;
begin
assign(input,fi); reset(input);
readln(n);
for i:=1 to n-1 do
begin
readln(b[i,0],b[i,1]);
inc(sl[b[i,0]]); inc(sl[b[i,1]]);
end;
pos[1]:=1; cur[1]:=1;
for i:=2 to n+1 do
begin
pos[i]:=pos[i-1]+sl[i-1];
cur[i]:=pos[i];
end;
for i:=1 to n-1 do
begin
a[cur[b[i,0]]]:=b[i,1]; a[cur[b[i,1]]]:=b[i,0];
inc(cur[b[i,0]]); inc(cur[b[i,1]]);
end;
close(input);
end;
procedure dfs(x:longint);
var i,j,min,k:longint;
begin
inc(dem); d[x]:=dem;
for i:=pos[x] to pos[x+1]-1 do
if d[a[i]]=0 then dfs(a[i]);
for j:=1 to 3 do
begin
f[j,x]:=j;
for i:=pos[x] to pos[x+1]-1 do
if d[a[i]]>d[x] then
begin
min:=maxlongint;
for k:=1 to 3 do
if (k<>j) and (f[k,a[i]]<min) then
min:=f[k,a[i]];
f[j,x]:=f[j,x]+min;
end;
end;
end;
procedure trace(x,y:longint);
var i,j,min:longint;
begin
d[x]:=0;
min:=maxlongint; j:=0;
for i:=1 to 3 do
if (i<>re[y]) and (f[i,x]<min) then
begin
min:=f[i,x];
j:=i;
end;
re[x]:=j;
for i:=pos[x] to pos[x+1]-1 do
if d[a[i]]<>0 then trace(a[i],x);
end;
procedure pr;
begin
dem:=0;
dfs(1);
trace(1,0);
end;
procedure wf;
var i:longint;
begin
assign(output,fo); rewrite(output);
writeln(f[re[1],1]);
for i:=1 to n do writeln(re[i]);
close(output);
end;
begin
rf;
pr;
wf;
end.