#include
     
      #include
      
       #include
       
        using namespace std;#define N 500001char s[N];int root;int tr[N][2];int m;int g[N][3],f[N][3];void dfs(int &rt){    rt=++m;    int tmp=s[m]-'0';    if(!tmp) return;    dfs(tr[rt][0]);    if(tmp>1) dfs(tr[rt][1]);}void DP(int rt){    if(!rt) return;    int l=tr[rt][0],r=tr[rt][1];    DP(l); DP(r);    int x,y,z;    for(int i=0;i<3;++i)    {        x=(i+1)%3; y=(x+1)%3; z= i ? 0 : 1;        g[rt][i]=max(g[l][x]+g[r][y],g[l][y]+g[r][x])+z;        f[rt][i]=min(f[l][x]+f[r][y],f[l][y]+f[r][x])+z;    }}int main(){    scanf("%s",s+1);    dfs(root);    DP(root);    printf("%d ",max(g[root][0],max(g[root][1],g[root][2])));    printf("%d",min(f[root][0],max(f[root][1],f[root][2])));}
       
      
     

 

1864: [Zjoi2006]三色二叉树

Time Limit: 1 Sec  Memory Limit: 64 MB

Submit: 1146  Solved: 844

[][][]

Description

Input

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

Output

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

Sample Input

1122002010

Sample Output

5 2