Description

Input

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

Output

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

Sample Input

1122002010

Sample Output

5 2

 

f[x][1\2\3]代表x点染红绿蓝色的最多有多少个点染成绿色

g[x][1\2\3]代表最少

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N (1000000+100) 5 using namespace std; 6 char st[N]; 7 int Father[N],Son[N][2]; 8 int a[N],maxn; 9 int f[N][4],g[N][4];10 11 void Build(int x,int fa)12 {13     maxn=max(maxn,x);14     Father[x]=fa;15     if (!Son[fa][0]) Son[fa][0]=x;16     else Son[fa][1]=x;17     if (a[x]>=1) Build(x+1,x);18     if (a[x]==2) Build(maxn+1,x);19 }20 21 void Dp(int x)22 {23     f[x][1]=0;f[x][2]=1;f[x][3]=0;24     g[x][1]=0;g[x][2]=1;g[x][3]=0;25     if (Son[x][0]) Dp(Son[x][0]);26     if (Son[x][1]) Dp(Son[x][1]);27     f[x][1]+=max( f[Son[x][0]][2]+f[Son[x][1]][3] , f[Son[x][0]][3]+f[Son[x][1]][2] );28     f[x][2]+=max( f[Son[x][0]][1]+f[Son[x][1]][3] , f[Son[x][0]][3]+f[Son[x][1]][1] );29     f[x][3]+=max( f[Son[x][0]][1]+f[Son[x][1]][2] , f[Son[x][0]][2]+f[Son[x][1]][1] );30     31     g[x][1]+=min( g[Son[x][0]][2]+g[Son[x][1]][3] , g[Son[x][0]][3]+g[Son[x][1]][2] );32     g[x][2]+=min( g[Son[x][0]][1]+g[Son[x][1]][3] , g[Son[x][0]][3]+g[Son[x][1]][1] );33     g[x][3]+=min( g[Son[x][0]][1]+g[Son[x][1]][2] , g[Son[x][0]][2]+g[Son[x][1]][1] );34 } 35 36 int main()37 {38     scanf("%s",st);39     for (int i=0;i<=strlen(st)-1;++i)40         a[i+1]=st[i]-'0';41     Build(1,0);42     Son[0][0]=Son[0][1]=0;43     Dp(1);44     printf("%d ",max(max(f[1][1],f[1][2]),f[1][3]));45     printf("%d",min(min(g[1][1],g[1][2]),g[1][3]));46 }