题目描述
输入输出格式
输入格式：
输入文件名：TRO.IN
输入文件仅有一行，不超过500000个字符，表示一个二叉树序列。
输出格式：
输出文件名：TRO.OUT
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
输入输出样例
输入样例#1： 复制
1122002010
输出样例#1： 复制
5 2
//Pro:P2585 [ZJOI2006]三色二叉树 //用mx[i][0~2]表示i这个点染绿、红、蓝色能获得的最大绿色数，mi表示最小绿色数 //如果这个点是叶节点，那么它的mx[][0]=mi[][0]=1,mx[][1]=mx[][2]=mi[][1]=mi[][2]=0 //如果有一个儿子或者两个儿子,可以看看下面代码被注释的部分 #include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; const int N=5e+5; char s[N]; struct NODE { int son[2],sson; int mx[3],mi[3]; //dp[0~2]分别表示绿、红、蓝 }p[N]; int now_node,root; void dfs1(int &u) //建树 { u=++now_node; p[u].sson=s[u]-'0'; for(int i=0;i<s[u]-'0';++i) dfs1(p[u].son[i]); } void dfs2(int u) { if(p[u].sson==0) { p[u].mx[0]=1,p[u].mx[1]=p[u].mx[2]=0; p[u].mi[0]=1,p[u].mi[1]=p[u].mi[2]=0; return; } for(int i=0;i<p[u].sson;++i) dfs2(p[u].son[i]); if(p[u].sson==1) { p[u].mx[0]=max(p[p[u].son[0]].mx[1],p[p[u].son[0]].mx[2])+1; //当前点绿色 p[u].mx[1]=max(p[p[u].son[0]].mx[0],p[p[u].son[0]].mx[2]); p[u].mx[2]=max(p[p[u].son[0]].mx[0],p[p[u].son[0]].mx[1]); p[u].mi[0]=min(p[p[u].son[0]].mi[1],p[p[u].son[0]].mi[2])+1; //当前点绿色 p[u].mi[1]=min(p[p[u].son[0]].mi[0],p[p[u].son[0]].mi[2]); p[u].mi[2]=min(p[p[u].son[0]].mi[0],p[p[u].son[0]].mi[1]); } if(p[u].sson==2) //有两个儿子，要考虑两个儿子不能相同 { p[u].mx[0]=max(p[p[u].son[0]].mx[1]+p[p[u].son[1]].mx[2],p[p[u].son[0]].mx[2]+p[p[u].son[1]].mx[1])+1; //当前点绿色 p[u].mx[1]=max(p[p[u].son[0]].mx[0]+p[p[u].son[1]].mx[2],p[p[u].son[0]].mx[2]+p[p[u].son[1]].mx[0]); //当前点红色 p[u].mx[2]=max(p[p[u].son[0]].mx[0]+p[p[u].son[1]].mx[1],p[p[u].son[0]].mx[1]+p[p[u].son[1]].mx[0]); //当前点蓝色 p[u].mi[0]=min(p[p[u].son[0]].mi[1]+p[p[u].son[1]].mi[2],p[p[u].son[0]].mi[2]+p[p[u].son[1]].mi[1])+1; //当前点绿色 p[u].mi[1]=min(p[p[u].son[0]].mi[0]+p[p[u].son[1]].mi[2],p[p[u].son[0]].mi[2]+p[p[u].son[1]].mi[0]); //当前点红色 p[u].mi[2]=min(p[p[u].son[0]].mi[0]+p[p[u].son[1]].mi[1],p[p[u].son[0]].mi[1]+p[p[u].son[1]].mi[0]); //当前点蓝色 } } int main() { scanf("%s",s+1); dfs1(root); dfs2(root); printf("%d %d",max(p[root].mx[0],max(p[root].mx[1],p[root].mx[2])),min(p[root].mi[0],min(p[root].mi[1],p[root].mi[2]))); return 0; }