记录编号	413078	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2017-06-10 18:44:55	内存使用	0.83 MiB

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
#define for1(a,b,i) for(int i=a;i<=b;i++)
#define for11(a,b,i)for(int i=a;i<b;i++)
#define for2(a,b,i) for(int i=a;i>=b;i--)
#define for22(a,b,i)for(int i=a;i>b;i--)
#define maxx(a,b) (a)>(b)?(a):(b)
#define minn(a,b) (a)<(b)?(a):(b)
char a[10010];
struct shu
{
   int ls,rs,fa,data,ji;
   shu(){ls=-1;rs=-1;fa=-1;data=0;ji=0;}       
}tree[10010];
int l;int fmax[10010][5],fmin[10010][5];
inline void wpyqsy()
{
   scanf("%s",&a);
   l=strlen(a);
   for2(l,1,i)
   {
     a[i]=a[i-1];tree[i].data=a[i]-'0';
     if(tree[i].data>0)
     {
       tree[i].ls=i+1;tree[i+1].fa=i;tree[i].ji+=1;                  
     }           
   }  
   tree[1].fa=0;
   for1(2,l,i)
     if(tree[i].fa==-1) 
         for2(i-1,1,j)
         if(tree[j].ji<tree[j].data)
         {
            tree[j].rs=i;tree[j].ji+=1;
            tree[i].fa=j;break;                          
         }  
   memset(fmax,0,sizeof(fmax));  
   memset(fmin,0,sizeof(fmin));                        
   return ;             
}//0 bu 1 xuan
inline void dp1(int x)
{
   fmax[x][0]=0;fmax[x][1]=1;
   if(tree[x].ls!=-1) dp1(tree[x].ls);
   if(tree[x].rs!=-1) dp1(tree[x].rs);
   if(tree[x].ls!=-1)
   {
     fmax[x][1]+=(fmax[tree[x].ls][0]+fmax[tree[x].rs][0]); 
     fmax[x][0]+=maxx(fmax[tree[x].ls][1]+fmax[tree[x].rs][0],fmax[tree[x].ls][0]+fmax[tree[x].rs][1]);                 
   }    
   return ;  
}
inline void dp2(int x)
{
   fmin[x][0]=0;fmin[x][1]=1;
   if(tree[x].ls!=-1) dp2(tree[x].ls);
   if(tree[x].rs!=-1) dp2(tree[x].rs);
   if(tree[x].ls!=-1)
   {
     fmin[x][1]+=(fmin[tree[x].ls][0]+fmin[tree[x].rs][0]); 
     fmin[x][0]+=minn(fmin[tree[x].ls][1]+fmin[tree[x].rs][0],fmin[tree[x].ls][0]+fmin[tree[x].rs][1]);                 
   }    
   return ;  
}
inline void love()
{
   dp1(1);dp2(1);return ;
}
int main()
{
    freopen("trot.in","r",stdin);
    freopen("trot.out","w",stdout);
    wpyqsy();
    love();
    fmax[1][2]=maxx(fmax[1][0],fmax[1][1]);
    fmin[1][2]=minn(fmin[1][0],fmin[1][1]);
    cout<<fmax[1][2]<<" "<<fmin[1][2]; 
    //while(1);
}