记录编号	296327	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-08-15 13:46:44	内存使用	0.85 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
void build(int&);
int dfsf(int,int);//min
int dfsg(int,int);//max
int n=0,rt,lch[maxn],rch[maxn],f[maxn][5],g[maxn][5],mn=~(1<<31),mx=(1<<31);
bool visf[maxn][5]={{false}},visg[maxn][5]={{false}};
int main(){
	freopen("trot.in","r",stdin);
	freopen("trot.out","w",stdout);
	build(rt);
	for(int i=1;i<=3;i++){
		mn=min(mn,dfsf(rt,i));
		mx=max(mx,dfsg(rt,i));
	}
	printf("%d %d",mx,mn);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
void build(int &x){
	x=++n;
	int cnt;
	scanf("%1d",&cnt);
	if(!cnt)return;
	if(cnt==1){
		build(lch[x]);
		rch[x]=0;
	}
	else if(cnt==2){
		build(lch[x]);
		build(rch[x]);
	}
}
int dfsf(int i,int j){
	if(visf[i][j])return f[i][j];
	visf[i][j]=true;
	if(!lch[i]&&!rch[i]){
		if(j==1)return f[i][j]=1;
		else return f[i][j]=0;
	}
	else if(!rch[i]){
		if(j==1)return f[i][j]=min(dfsf(lch[i],2),dfsf(lch[i],3))+1;
		else if(j==2)return f[i][j]=min(dfsf(lch[i],1),dfsf(lch[i],3));
		else return f[i][j]=min(dfsf(lch[i],1),dfsf(lch[i],2));
	}
	else{
		if(j==1)return f[i][j]=min(dfsf(lch[i],2)+dfsf(rch[i],3),dfsf(lch[i],3)+dfsf(rch[i],2))+1;
		else if(j==2)return f[i][j]=min(dfsf(lch[i],1)+dfsf(rch[i],3),dfsf(lch[i],3)+dfsf(rch[i],1));
		else return f[i][j]=min(dfsf(lch[i],1)+dfsf(rch[i],2),dfsf(lch[i],2)+dfsf(rch[i],1));
	}
}
int dfsg(int i,int j){
	if(visg[i][j])return g[i][j];
	visg[i][j]=true;
	if(!lch[i]&&!rch[i]){
		if(j==1)return g[i][j]=1;
		else return g[i][j]=0;
	}
	else if(!rch[i]){
		if(j==1)return g[i][j]=max(dfsg(lch[i],2),dfsg(lch[i],3))+1;
		else if(j==2)return g[i][j]=max(dfsg(lch[i],1),dfsg(lch[i],3));
		else return g[i][j]=max(dfsg(lch[i],1),dfsg(lch[i],2));
	}
	else{
		if(j==1)return g[i][j]=max(dfsg(lch[i],2)+dfsg(rch[i],3),dfsg(lch[i],3)+dfsg(rch[i],2))+1;
		else if(j==2)return g[i][j]=max(dfsg(lch[i],1)+dfsg(rch[i],3),dfsg(lch[i],3)+dfsg(rch[i],1));
		else return g[i][j]=max(dfsg(lch[i],1)+dfsg(rch[i],2),dfsg(lch[i],2)+dfsg(rch[i],1));
	}
}
/*
1122002010
Answer:
5 2
*/