记录编号	552969	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	fw	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2020-08-09 20:38:24	内存使用	4.71 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 10001;
int f[MAXN][3];// f[i][0] 表示当前节点染成 蓝色 的最大绿色数  
               // f[i][1] 表示 红色  
			   // f[i][2] 表示 绿色 
int dp[MAXN][3];// dp 同理 最小 
char ss[MAXN];
int n = 0,p = 0;
int lc[MAXN] = {0},rc[MAXN] = {0};// lc [i] 存 i 的左孩子 rc [i] 存 i 的右孩子   
void init () {//递归建树，不太好理解， 
	p ++;
	n ++;
	int now = n;
	if (ss[p] == '2') lc[now] = n + 1,init (),rc[now] = n + 1,init ();//先建左子树，再建右子树 
	if (ss[p] == '1') lc[now] = n + 1,init ();                        //只有单个节点只建左子树 
}
void dfs_max (int u) {
	if (u == 0) return ; //空节点 返回 
	f[u][0] = 0;
	f[u][1] = 0;  // 当前节点初始化 染成 绿色 直接为 1 
	f[u][2] = 1;
	dfs_max (lc[u]); dfs_max (rc[u]); // 向下遍历 
	f[u][0] += max (f[rc[u]][1] + f[lc[u]][2],f[rc[u]][2] + f[lc[u]][1]); // 儿子可以染另外两种颜色
	f[u][1] += max (f[rc[u]][0] + f[lc[u]][2],f[rc[u]][2] + f[lc[u]][0]);
	f[u][2] += max (f[rc[u]][0] + f[lc[u]][1],f[lc[u]][0] + f[rc[u]][1]);
	return ; 
}
void dfs_min (int u) {
	if (u == 0) return ; //空节点 返回 
	dp[u][0] = 0;
	dp[u][1] = 0;  // 当前节点初始化 染成 绿色 直接为 1 
	dp[u][2] = 1;
	dfs_min (lc[u]); dfs_min (rc[u]); // 向下遍历 
	dp[u][0] += min (dp[rc[u]][1] + dp[lc[u]][2],dp[rc[u]][2] + dp[lc[u]][1]); // 儿子可以染另外两种颜色
	dp[u][1] += min (dp[rc[u]][0] + dp[lc[u]][2],dp[rc[u]][2] + dp[lc[u]][0]);
	dp[u][2] += min (dp[rc[u]][0] + dp[lc[u]][1],dp[lc[u]][0] + dp[rc[u]][1]);
	return ; 
}
int main () {
	freopen("trot.in","r",stdin);
	freopen("trot.out","w",stdout);
	memset (dp,0,sizeof (dp));
	scanf("%s",ss + 1);             //读入字符串 
	init ();            //先建树 
	dfs_max (1);
	printf ("%d ",max (f[1][0],max (f[1][1],f[1][2])));
	dfs_min (1);
	printf ("%d\n",min (dp[1][0],min (dp[1][1],dp[1][2])));
	return 0;
}