记录编号	119645	评测结果	AAAAAAAAAAAAA
题目名称	237.[POI 1999/ZJOI 2006] 三色二叉树	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2014-09-13 11:57:18	内存使用	0.64 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define Maxn 20003
using namespace std;
class tree{
	public:
	int da,lc,rc;
	void push(int x){
		if(lc!=0) rc=x;
		else lc=x;
	}
}T[Maxn]={0};
int tot=0,fw[Maxn]={0},fb[Maxn]={0};
int Dp_w(int),Dp_b(int),Dp_w0(int),Dp_b0(int);
string s;
void build(int now){
	tot++;
	if(s[tot]!='0'){
		if(s[tot]=='1'){
			T[now].push(tot+1); build(tot+1);
			return;
		}
		T[now].push(tot+1); build(tot+1);
		T[now].push(tot+1); build(tot+1);
	}
}
int Dp_b(int now){
	if(now==0 || fb[now]) return fb[now];
	int t1=Dp_b(T[now].rc)+Dp_w(T[now].lc);
	int t2=Dp_w(T[now].rc)+Dp_b(T[now].lc);
	fb[now]=max(t1,t2);
	return fb[now];
}

int Dp_w(int now){
	if(now==0 || fw[now]) return fw[now];
	fw[now]=Dp_b(T[now].rc)+Dp_b(T[now].lc)+1;
	return fw[now];
}
int Dp_b0(int now){
	if(now==0 || fb[now]) return fb[now];
	if(!T[now].rc) fb[now]=Dp_b0(T[now].lc);
	else{
		int t1=Dp_b0(T[now].rc)+Dp_w0(T[now].lc);
		int t2=Dp_w0(T[now].rc)+Dp_b0(T[now].lc);
		fb[now]=min(t1,t2);
	}
	return fb[now];
}
int Dp_w0(int now){
	if(now==0 || fw[now]) return fw[now];
	fw[now]=Dp_b0(T[now].rc)+Dp_b0(T[now].lc)+1;
	return fw[now];
}
void init(){
	ios::sync_with_stdio(false);
	cin>>s;s="*"+s;
	build(1);
	cout<<max(Dp_w(1),Dp_b(1))<<' ';
	memset(fw,0,sizeof(fw));
	memset(fb,0,sizeof(fb));
	cout<<min(Dp_w0(1),Dp_b0(1))<<endl;
}
int main(){
	freopen("trot.in","r",stdin);
	freopen("trot.out","w",stdout);
	init();
	return 0;
}