记录编号	116606	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2014-08-26 11:58:18	内存使用	1.89 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct node
{
  int rc,lc;
  node()
  {
    lc=rc=0;
  }
}tree[50000];
//==============var declaration=================
char num[50000];
int maxv[50000][3],minv[50000][3];
int top=1;
//==============function declaration============
void maketree(int o);
void dp(int x,int color);
//==============main code=======================
int main()
{  
  string FileName="trot";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
#endif    
  maketree(1);
  memset(maxv,-1,sizeof(maxv));
  For(i,1,top)
    For(j,0,2)
      minv[i][j]=INF;
  dp(1,0);
  dp(1,1);
  dp(1,2);
  printf("%d %d\n",max(max(maxv[1][0],maxv[1][1]),maxv[1][2]),min(min(minv[1][1],minv[1][2]),minv[1][0]));
  return 0;
}
//================fuction code====================
void maketree(int o)
{
  char ch=getchar();
  if (ch=='0')
  {
    tree[o].lc=tree[o].rc=0;
    return;
  }
  if (ch=='1')
  {
    tree[o].rc=0;
    tree[o].lc=++top;
    maketree(top);
  }  
  if (ch=='2')
  {
    tree[o].lc=++top;
    maketree(top);
    tree[o].rc=++top;
    maketree(top);
  }
}
void dp(int x,int color)
{
  if (maxv[x][color]!=-1) return ;
  if (tree[x].lc==0&&tree[x].rc==0)
  {
    if (color==0)
      minv[x][color]=maxv[x][color]=1;
    else
      minv[x][color]=maxv[x][color]=0;
    return ;
  }
  if (tree[x].rc==0)
  {
    if (color==0)
    {
      dp(tree[x].lc,1);
      dp(tree[x].lc,2);
      maxv[x][color]=max(maxv[x][color],max(maxv[tree[x].lc][1],maxv[tree[x].lc][2])+1);
      minv[x][color]=min(minv[x][color],min(minv[tree[x].lc][1],minv[tree[x].lc][2])+1);
    }
    if (color==1)
    {
      dp(tree[x].lc,0);
      dp(tree[x].lc,2);
      maxv[x][color]=max(maxv[x][color],max(maxv[tree[x].lc][0],maxv[tree[x].lc][2]));
      minv[x][color]=min(minv[x][color],min(minv[tree[x].lc][0],minv[tree[x].lc][2]));
    }
    if (color==2)
    {
      dp(tree[x].lc,1);
      dp(tree[x].lc,0);
      maxv[x][color]=max(maxv[x][color],max(maxv[tree[x].lc][0],maxv[tree[x].lc][1]));
      minv[x][color]=min(minv[x][color],min(minv[tree[x].lc][0],minv[tree[x].lc][1]));
    }
    return ;
  }
  if (color==0)
  {
      dp(tree[x].lc,1);dp(tree[x].lc,2);
      dp(tree[x].rc,1);dp(tree[x].rc,2);
      maxv[x][color]=max(maxv[x][color],max(maxv[tree[x].lc][1]+maxv[tree[x].rc][2]+1,maxv[tree[x].lc][2]+maxv[tree[x].rc][1]+1));
      minv[x][color]=min(minv[x][color],min(minv[tree[x].lc][1]+minv[tree[x].rc][2]+1,minv[tree[x].lc][2]+minv[tree[x].rc][1]+1));
  }
  if (color==1)
  {
    dp(tree[x].lc,2);dp(tree[x].lc,0);
    dp(tree[x].rc,2);dp(tree[x].rc,0);
    maxv[x][color]=max(maxv[x][color],max(maxv[tree[x].lc][2]+maxv[tree[x].rc][0],maxv[tree[x].lc][0]+maxv[tree[x].rc][2]));
    minv[x][color]=min(minv[x][color],min(minv[tree[x].lc][2]+minv[tree[x].rc][0],minv[tree[x].lc][0]+minv[tree[x].rc][2]));
  }
  if (color==2)
  {
    dp(tree[x].lc,0);dp(tree[x].lc,1);
    dp(tree[x].rc,0);dp(tree[x].rc,1);
    maxv[x][color]=max(maxv[x][color],max(maxv[tree[x].lc][0]+maxv[tree[x].rc][1],maxv[tree[x].lc][1]+maxv[tree[x].rc][0]));
    minv[x][color]=min(minv[x][color],min(minv[tree[x].lc][0]+minv[tree[x].rc][1],minv[tree[x].lc][1]+minv[tree[x].rc][0]));
  }
}