bzoj1864 [Zjoi2006]三色二叉树

Description

Input

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

Output

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

Sample Input

1122002010

Sample Output

5 2

树形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>

#define MAX 300010

int f[MAX][2];

int l[MAX],r[MAX];

int treesize=1;

inline int max(int a,int b)

{return a>b?a:b;}

inline int min(int a,int b)

{return a<b?a:b;}

inline 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 dp1(int now)

{

	if (!now)return;

	dp1(r[now]);dp1(l[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[l[now]][1]+f[r[now]][0]);

}

inline void dp2(int now)

{

	if (!now)return;

	dp2(r[now]);dp2(l[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[l[now]][1]+f[r[now]][0]);

}

int main()

{

	read(1);

	dp1(1);

	printf("%d ",max(f[1][0],f[1][1]));

	for (int i=1;i<=treesize;i++){f[i][0]=0;f[i][1]=0;}

	dp2(1);

	printf("%d\n",min(f[1][0],f[1][1]));

}

巴特西