CTREE - Tô màu nhỏ nhất

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
program CTREE;
const
  FINP='';
  FOUT='';
  MAXN=10001;
var
  father,xet,a,start,deg,dx,eu,ev:array[1..MAXN] of longint;
  d:array[1..MAXN,1..3] of longint;
  ke:array[1..MAXN*2] of longint;
  kq,n:longint;
function min(a,b:longint):longint;
begin
  if a<b then min:=a else min:=b;
end;
procedure inp;
var
  f:text;
  i,u,v:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  for i:=1 to n-1 do
    begin
      readln(f,u,v);
      inc(deg[u]); inc(deg[v]);
      eu[i]:=u; ev[i]:=v;
    end;
  close(f);
end;
procedure init;
var
  i,u,v:longint;
begin
  start[1]:=1;
  for i:=2 to n+1 do start[i]:=start[i-1]+deg[i-1];
  for i:=1 to n-1 do
    begin
      u:=eu[i]; v:=ev[i];
      ke[start[u]+dx[u]]:=v;
      ke[start[v]+dx[v]]:=u;
      inc(dx[u]); inc(dx[v]);
    end;
end;
procedure ans;
var
  f:text;
  i:longint;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  for i:=1 to n do
    writeln(f,a[i]);
  close(f);
end;
procedure DFS1(u:longint);
var
  i,v,j:longint;
begin
  xet[u]:=1;
  d[u,1]:=1; d[u,2]:=2; d[u,3]:=3;
  for i:=start[u] to start[u+1]-1 do
    begin
      v:=ke[i];
      if xet[v]=1 then continue;
      DFS1(v);
      father[v]:=u;
      d[u,1]:=d[u,1]+min(d[v,2],d[v,3]);
      d[u,2]:=d[u,2]+min(d[v,1],d[v,3]);
      d[u,3]:=d[u,3]+min(d[v,1],d[v,2]);
    end;
end;
procedure DFS2(u:longint);
var
  i,v:longint;
begin
  xet[u]:=1;
  for i:=start[u] to start[u+1]-1 do
    begin
      v:=ke[i];
      if xet[v]=1 then continue;
      case a[u] of
        1: begin if d[v,2]<d[v,3] then a[v]:=2 else a[v]:=3; end;
        2: begin if d[v,1]<d[v,3] then a[v]:=1 else a[v]:=3; end;
        3: begin if d[v,1]<d[v,2] then a[v]:=1 else a[v]:=2; end;
      end;
      DFS2(v);
    end;
end;
procedure solve;
begin
  DFS1(1);
  kq:=d[1,1]; a[1]:=1;
  if d[1,2]<kq then begin kq:=d[1,2]; a[1]:=2; end;
  if d[1,3]<kq then begin kq:=d[1,3]; a[1]:=3; end;
  fillchar(xet,sizeof(xet),0);
  DFS2(1);
end;
begin
  inp;
  init;
  solve;
  ans;
end.

Download