P83831

三色二叉树

难度 6 级 初三 动态规划入门 树形
讨论 统计 2通过 2提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

例如,下图所表示的二叉树可以用二叉树序列 S=\texttt{21200110} 来表示。

haha.png

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

输入

输入只有一行一个字符串 s,表示二叉树序列。

输出

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

样例

样例 1
输入
1122002010
输出
5 2

提示

对于全部的测试点,保证 1 \leq |s| \leq 5 \times 10^5,s 中只含字符 0 1 2。

来源

省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交