ac1181.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1181;
const
  maxn=50000;
  maxlab=10;
var
  v2:array[1..maxn*2-2]of word;
  pre:array[1..maxn*2-2]of longint;
  last:array[1..maxn]of longint;
  v:array[1..maxn]of boolean;
  score:array[1..maxn,1..2]of cardinal;
  lab:array[1..maxn,1..2]of byte;
  n,i,x,y:word;
procedure dp(x:word);
  var
    p,l,s:longint;
    b:boolean;
  begin
    v[x]:=true;
    while (last[x]>0) and v[v2[last[x]]] do last[x]:=pre[last[x]];
    p:=last[x];
    while p>0 do begin
      if v[v2[p]] then
        pre[s]:=pre[p]
      else begin
        dp(v2[p]);s:=p;
      end;
      p:=pre[p];
    end;
    for l:=1 to maxlab do begin
      b:=false;
      p:=last[x];s:=l;
      while p>0 do begin
        if lab[v2[p],1]=l then begin
          b:=true;inc(s,score[v2[p],2]);
        end
        else
          inc(s,score[v2[p],1]);
        p:=pre[p];
      end;
      if s<score[x,1] then begin
        score[x,2]:=score[x,1];lab[x,2]:=lab[x,1];
        score[x,1]:=s;lab[x,1]:=l;
      end
      else if s<score[x,2] then begin
        score[x,2]:=s;lab[x,2]:=l;
      end;
      if (l>1) and not b then break;
    end;
  end;
begin
  repeat
    fillchar(last,sizeof(last),0);
    fillchar(v,sizeof(v),0);
    fillchar(score,sizeof(score),255);
    read(n);
    for i:=1 to n-1 do begin
      read(x,y);
      v2[i*2-1]:=y;pre[i*2-1]:=last[x];last[x]:=i*2-1;
      v2[i*2]:=x;pre[i*2]:=last[y];last[y]:=i*2;
    end;
    dp(1);
    writeln(score[1,1]);
  until seekeof;
end.