难得的ZJOI水题...DFS一遍就行了...
-----------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
const int maxn = 500009;
int N = 0, Mx[maxn][3], Mn[maxn][3], L[maxn], R[maxn];
void dfs(int x) {
char c = getchar();
if(c != '0') {
dfs(L[x] = N++);
if(c == '2') dfs(R[x] = N++);
}
}
void DFS(int x) {
if(~L[x]) DFS(L[x]);
if(~R[x]) DFS(R[x]);
if(~L[x] && ~R[x]) {
Mx[x][0] = max(Mx[L[x]][1] + Mx[R[x]][2], Mx[L[x]][2] + Mx[R[x]][1]) + 1;
Mx[x][1] = max(Mx[L[x]][0] + Mx[R[x]][2], Mx[L[x]][2] + Mx[R[x]][0]);
Mx[x][2] = max(Mx[L[x]][0] + Mx[R[x]][1], Mx[L[x]][1] + Mx[R[x]][0]);
Mn[x][0] = min(Mn[L[x]][1] + Mn[R[x]][2], Mn[L[x]][2] + Mn[R[x]][1]) + 1;
Mn[x][1] = min(Mn[L[x]][0] + Mn[R[x]][2], Mn[L[x]][2] + Mn[R[x]][0]);
Mn[x][2] = min(Mn[L[x]][0] + Mn[R[x]][1], Mn[L[x]][1] + Mn[R[x]][0]);
} else if(~L[x]) {
Mx[x][0] = max(Mx[L[x]][1], Mx[L[x]][2]) + 1;
Mx[x][1] = max(Mx[L[x]][0], Mx[L[x]][2]);
Mx[x][2] = max(Mx[L[x]][1], Mx[L[x]][0]);
Mn[x][0] = min(Mn[L[x]][1], Mn[L[x]][2]) + 1;
Mn[x][1] = min(Mn[L[x]][0], Mn[L[x]][2]);
Mn[x][2] = min(Mn[L[x]][1], Mn[L[x]][0]);
} else if(~R[x]) {
Mx[x][0] = max(Mx[R[x]][1], Mx[R[x]][2]) + 1;
Mx[x][1] = max(Mx[R[x]][0], Mx[R[x]][2]);
Mx[x][2] = max(Mx[R[x]][1], Mx[R[x]][0]);
Mn[x][0] = min(Mn[R[x]][1], Mn[R[x]][2]) + 1;
Mn[x][1] = min(Mn[R[x]][0], Mn[R[x]][2]);
Mn[x][2] = min(Mn[R[x]][1], Mn[R[x]][0]);
} else {
Mx[x][1] = Mx[x][2] = 0; Mx[x][0] = 1;
Mn[x][1] = Mn[x][2] = 0; Mn[x][0] = 1;
}
}
int main() {
memset(L, -1, sizeof L);
memset(R, -1, sizeof R);
dfs(N++); DFS(0);
printf("%d %d\n", *max_element(Mx[0], Mx[0] + 3), *min_element(Mn[0], Mn[0] + 3));
return 0;
}
-----------------------------------------------------------------------
1864: [Zjoi2006]三色二叉树
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 590 Solved: 412
[Submit][Status][Discuss]
Description
Input
仅有一行，不超过500000个字符，表示一个二叉树序列。
Output
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2