[POI1999]三色二叉树

成绩 0 开启时间 2013年01月22日 星期二 10:20
折扣 0.8 折扣时间 2013年01月22日 星期二 10:20
允许迟交 是 关闭时间 2013年01月22日 星期二 10:20
输入文件 trot.in 输出文件 trot.out

问题描述

一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”：

  • 0 该树没有子节点
  • 1S1 该树有一个子节点，S1为其二叉树序列
  • 1S1S2 该树有两个子节点，S1,S2分别为两个二叉树的序列

例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。

Image:Trot.gif

你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入文件


输入文件仅有一行，不超过10000个字符，表示一个二叉树序列。

输出文件

输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

样例输入 

1122002010

样例输出 

5 2