#P2585. [ZJOI2006] 三色二叉树

    ID: 1593 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp搜索2006各省省选浙江深度优先搜索DFS

[ZJOI2006] 三色二叉树

题目描述

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

$$S= \begin{cases} 0& \text表示该树没有子节点\\ 1S_1& 表示该树有一个节点,S_1 为其子树的二叉树序列\\ 2S_1S_2& 表示该树由两个子节点,S_1 和 S_2 分别表示其两个子树的二叉树序列 \end{cases}$$

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

haha.png

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

输入格式

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

输出格式

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

1122002010
5 2

提示

数据规模与约定

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