记录编号	15260	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	Pascal	运行时间	0.016 s
提交时间	2009-11-11 12:50:01	内存使用	0.29 MiB

program xmz;
var
f1,f2:text;
x:array[1..10000]of integer;
f:array[1..10000,1..2]of integer;
fd,fs:array[1..10000,1..3]of integer;
y:array[1..10000]of boolean;
n,maxx,a:longint;
t:char;
function min(i,j:integer):integer;
 begin
  if i<j then min:=i else min:=j;
 end;

function max(i,j:integer):integer;
 begin
  if i>j then max:=i else max:=j;
 end;


procedure mt(nn:longint);
 var
 i:integer;
 begin
  for i:=1 to x[nn] do
   begin
    f[nn,i]:=n+1;
    read(f1,t);inc(n);
    x[n]:=ord(t)-48;
    mt(n);
   end;
 end;

procedure suan(nn:longint);
 var
 i:integer;
 begin
  if x[nn]=0 then
   begin
    fd[nn,1]:=1;fs[nn,1]:=1;fd[nn,2]:=0;fd[nn,3]:=0;
    fs[nn,2]:=0;fs[nn,3]:=0;
   end
   else
   begin
    for i:=1 to x[nn] do if (not y[f[nn,i]]) then suan(f[nn,i]);
    if x[nn]=1 then
     begin
     fd[nn,1]:=max(fd[f[nn,1],2],fd[f[nn,1],3])+1;
     fs[nn,1]:=min(fs[f[nn,1],2],fs[f[nn,1],3])+1;
     fd[nn,2]:=max(fd[f[nn,1],1],fd[f[nn,1],3]);
     fs[nn,2]:=min(fs[f[nn,1],1],fs[f[nn,1],3]);
     fd[nn,3]:=max(fd[f[nn,1],2],fd[f[nn,1],1]);
     fs[nn,3]:=min(fs[f[nn,1],2],fs[f[nn,1],1]);
     end;
    if x[nn]=2 then
     begin
      fd[nn,1]:=max(fd[f[nn,1],2]+fd[f[nn,2],3],fd[f[nn,1],3]+fd[f[nn,2],2])+1;
      fs[nn,1]:=min(fs[f[nn,1],2]+fs[f[nn,2],3],fs[f[nn,1],3]+fs[f[nn,2],2])+1;
      fd[nn,2]:=max(fd[f[nn,1],1]+fd[f[nn,2],3],fd[f[nn,1],3]+fd[f[nn,2],1]);
      fs[nn,2]:=min(fs[f[nn,1],1]+fs[f[nn,2],3],fs[f[nn,1],3]+fs[f[nn,2],1]);
      fd[nn,3]:=max(fd[f[nn,1],2]+fd[f[nn,2],1],fd[f[nn,1],1]+fd[f[nn,2],2]);
      fs[nn,3]:=min(fs[f[nn,1],2]+fs[f[nn,2],1],fs[f[nn,1],1]+fs[f[nn,2],2]);
     end;
   end;
  y[nn]:=true;
 end;
begin
 assign(f1,'trot.in');assign(f2,'trot.out');
 reset(f1);rewrite(f2);
 read(f1,t);
 x[1]:=ord(t)-48;
 n:=1;
 mt(n);
 suan(1);
 maxx:=0;
 for a:=1 to 3 do
  if fd[1,a]>maxx then maxx:=fd[1,a];
 write(f2,maxx,' ');
 maxx:=maxint;
 for a:=1 to 3 do
  if fs[1,a]<maxx then maxx:=fs[1,a];
 write(f2,maxx);

 close(f1);close(f2);
end.