记录编号	15330	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	bing	是否通过	通过
代码语言	Pascal	运行时间	2.329 s
提交时间	2009-11-11 19:07:55	内存使用	95.65 MiB

program bing;
type
 dian=record
 l,r,d:integer;
end;
var
 f1,f2:text;
 dm:integer;
 xt,kt:integer;
 a:array[1..10000] of char;
 t:array[1..10000] of dian;
 b:array[0..10000,0..5000] of integer;
 f:array[0..10000,0..1,0..1] of integer;
procedure bl(x:integer);
var
 de:integer;
begin
 if a[x]<>'0' then
 begin
  inc(xt);
  t[x].l:=xt;
  t[xt].d:=t[x].d+1;
  de:=t[xt].d;
  if de>dm then dm:=de;
  inc(b[de,0]);
  b[de,b[de,0]]:=xt;
  bl(xt);
  if a[x]='2' then
   begin
    inc(xt);
    t[x].r:=xt;
    t[xt].d:=t[x].d+1;
    de:=t[xt].d;
    if de>dm then dm:=de;
    inc(b[de,0]);
    b[de,b[de,0]]:=xt;
    bl(xt);
   end;
 end;
end;
procedure init;
var
 de:integer;
begin
 assign(f1,'trot.in');reset(f1);
 assign(f2,'trot.out');rewrite(f2);
 kt:=0;
 fillchar(t,sizeof(t),0);
 fillchar(b,sizeof(b),0);
 b[0,0]:=1;b[0,1]:=1;
 while not eof(f1) do
 begin
  inc(kt);
  read(f1,a[kt]);
 end;
 xt:=1;
 bl(1);

end;
procedure nb;
var
 i,j,k:integer;
begin
 for i:=1 to kt do
 if a[i]='0' then
 begin
  f[i,0,1]:=0;f[i,1,1]:=1;
  f[i,0,0]:=0;f[i,1,0]:=1;
 end;
 for i:=dm-1 downto 0 do
 for j:=1 to  b[i,0] do
 if a[b[i,j]]<>'0' then
 begin
  k:=b[i,j];
  if f[t[k].l,0,1]+f[t[k].r,1,1]>f[t[k].l,1,1]+f[t[k].r,0,1]
  then f[k,0,1]:=f[t[k].l,0,1]+f[t[k].r,1,1]
  else f[k,0,1]:=f[t[k].l,1,1]+f[t[k].r,0,1];
  f[k,1,1]:=f[t[k].l,0,1]+f[t[k].r,0,1]+1;
  if f[t[k].l,0,0]+f[t[k].r,1,0]<f[t[k].l,1,0]+f[t[k].r,0,0]
  then f[k,0,0]:=f[t[k].l,0,0]+f[t[k].r,1,0]
  else f[k,0,0]:=f[t[k].l,1,0]+f[t[k].r,0,0];
  f[k,1,0]:=f[t[k].l,0,0]+f[t[k].r,0,0]+1;
 end;
end;
begin
 init;
 nb;
 if f[1,1,1]>f[1,0,1] then write(f2,f[1,1,1],' ') else write(f2,f[1,0,1]);
 if f[1,1,0]<f[1,0,0] then write(f2,f[1,1,0]) else write(f2,f[1,0,0]);
 close(f1);close(f2);
end.