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.

Download