【BZOJ 1864】【ZJOI 2006】三色二叉树【树型DP】

Description

Input

仅有一行，不超过500000个字符，表示一个二叉树序列。

Output

输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

题解

一道树形dp题（类似《没有上司的舞会》） 对于求最大值

f[i][0]表示i这个点不染绿色，i下面的子树最多能取多少个绿色的点 f[i][1]表示i这个点染了绿色，i下面的子树最多能取多少个绿色的点

考虑每一个点 如果染了绿色，那么根据题目所述，它的左右儿子必须染得跟它不一样，就是必须不是绿色 　　f[i][1]=f[ r[i] ][0]+f[ l[i] ][0]+1

然后如果这个点不染绿色，那么一个节点与其左右儿子必须颜色不同，就是说必须红绿蓝各一，那么还是只有一个绿色 所以枚举从左右儿子中哪一个转移过来就好了 　　所以f[i][0]=max(f[ l[i] ][0]+f[ r[i] ][1],f[ l[i] ][1]+f[ r[i] ][0])

最小值同理

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 500010 char c[N]; int f[N][2],l[N],r[N]; int treesize = 1; void read(int now) { char ch = getchar(); if(ch == '0') return; treesize++; l[now] = treesize; read(treesize); if(ch == '2') { treesize++; r[now] = treesize; read(treesize); } } inline void dp_max(int now) { if(!now) return; dp_max(l[now]);dp_max(r[now]); f[now][1] = f[l[now]][0] + f[r[now]][0] + 1; f[now][0] = max(f[l[now]][0]+f[r[now]][1],f[r[now]][0]+f[l[now]][1]); } inline void dp_min(int now) { if(!now) return; dp_min(l[now]);dp_min(r[now]); f[now][1] = f[l[now]][0] + f[r[now]][0] + 1; f[now][0] = min(f[l[now]][0]+f[r[now]][1],f[r[now]][0]+f[l[now]][1]); } int main() { read(1); dp_max(1); printf("%d ",max(f[1][0],f[1][1])); memset(f,0,sizeof(f)); dp_min(1); printf("%d\n",min(f[1][0],f[1][1])); return 0; }