记录编号	15325	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	ZhouZn1	是否通过	通过
代码语言	Pascal	运行时间	0.047 s
提交时间	2009-11-11 18:51:57	内存使用	1.03 MiB

program trot;
type
        rec=record
        l,r,f:longint;
        end;
var
        ss:ansistring;
        i,j,p,l:longint;
        tree:array[0..40005]of rec;
        f:array[1..40005,1..3]of longint;
procedure init;
begin
        assign(input,'trot.in');
        reset(input);
        assign(output,'trot.out');
        rewrite(output);
        readln(ss);
        l:=length(ss);
end;
procedure closef;
begin
        close(input);
        close(output);
end;
function max(a,b:longint):longint;
begin
        if a>b then exit(a) else exit(b);
end;

function min(a,b:longint):longint;
begin
        if a<b then exit(a) else exit(b);
end;
procedure settree(fa:longint);
begin
        inc(p);
        if p>l then exit;
        if ss[fa]='1' then
        begin
                tree[fa].l:=p;
                tree[p].f:=fa;
                settree(p);
        end else if ss[fa]='2' then
        begin
                tree[fa].l:=p;
                tree[p].f:=fa;
                settree(p);
                inc(p);
                tree[fa].r:=p;
                tree[p].f:=fa;
                settree(p);
        end;
        if ss[fa]='0' then
        begin
        dec(p);
        exit;
        end;
end;
procedure init1;
begin
        fillchar(f,sizeof(f),0);
        for i:=1 to p do
        if (tree[i].l=0)and(tree[i].r=0) then
        f[i,2]:=1;
end;
procedure dp1(x:longint);
begin
        if tree[x].l<>0 then
        begin
        dp1(tree[x].l);
        if tree[x].l<>0 then
        begin
        f[x,1]:=max(f[tree[x].l,3],f[tree[x].l,2]);
        f[x,2]:=max(f[tree[x].l,1],f[tree[x].l,3])+1;
        f[x,3]:=max(f[tree[x].l,1],f[tree[x].l,2]);
        end;
        end;
        if tree[x].r<>0 then
        begin
        dp1(tree[x].r);
        f[x,1]:=max(f[tree[x].l,2]+f[tree[x].r,3],f[tree[x].l,3]+f[tree[x].r,2]);
        f[x,2]:=max(f[tree[x].l,1]+f[tree[x].r,3],f[tree[x].l,3]+f[tree[x].r,1])+1;
        f[x,3]:=max(f[tree[x].l,1]+f[tree[x].r,2],f[tree[x].l,2]+f[tree[x].r,1]);
        end;
end;
procedure dp2(x:longint);
begin
        if tree[x].l<>0 then
        begin
        dp2(tree[x].l);
        if tree[x].l<>0 then
        begin
        f[x,1]:=min(f[tree[x].l,3],f[tree[x].l,2]);
        f[x,2]:=min(f[tree[x].l,1],f[tree[x].l,3])+1;
        f[x,3]:=min(f[tree[x].l,1],f[tree[x].l,2]);
        end;
        end;
        if tree[x].r<>0 then
        begin
        dp2(tree[x].r);
        f[x,1]:=min(f[tree[x].l,2]+f[tree[x].r,3],f[tree[x].l,3]+f[tree[x].r,2]);
        f[x,2]:=min(f[tree[x].l,1]+f[tree[x].r,3],f[tree[x].l,3]+f[tree[x].r,1])+1;
        f[x,3]:=min(f[tree[x].l,1]+f[tree[x].r,2],f[tree[x].l,2]+f[tree[x].r,1]);
        end;
end;
procedure main;
begin
        fillchar(tree,sizeof(tree),0);
        p:=1;
        settree(1);
        dec(p);
        init1;
        dp1(1);
        write(max(f[1,2],max(f[1,1],f[1,2])),' ');
        init1;
        dp2(1);
        writeln(min(f[1,3],min(f[1,1],f[1,2])));
end;
begin
        init;
        main;
        closef;
end.