Description:


Input:


仅有一行,不超过500000个字符,表示一个二叉树序列。

Output:


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

Sample Input:


Sample Output:


题解:


注意一下这个“二叉树序列”的特点。
因为对于一个节点,我们交换它的左右子树,答案是不会改变的。
所以我们不妨设S1就是左子树,S2就是右子树。
然后该序列就唯一对应一棵二叉树,我们把它构造出来。
接下来就可以树形DP了。
设dp[i][j]为以i为根节点的子树当i染色为j时最多(最少)有多少个0颜色的节点。
然后两次dp就可以了。

用记忆化搜索做TLE了两发。
改成循环就过了。