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;
}