题解 P2585 【[ZJOI2006]三色二叉树】
消失的海岸线
2017-09-20 13:56:28
**在此给出一个相对较简的实现**
人话题意：递归地给出一棵二叉树，节点的颜色可以是0,1,2，父子节点、兄弟节点间的颜色不同，求最多（最少）可以有多少个点为0色。
朴素的树形dp，读入数据是比较麻烦的。
可以发现实际上只有绿和不为绿两种状态，最大/最小做两遍即可，在此以最大为例：
以 $f_{i}$ 表示点 $i$ 为绿色时最多有多少点可以为绿，$g_{i}$ 表示点 $i$ 不为绿色时最多多少点可以为绿。
转移是这样的，设当前节点为 $i$ ，若为绿色，则子节点必须非绿。若不为绿色，则从两个儿子分别一绿一不绿的状态取 $max$ 转移而来。
代码如下：
```cpp
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define N 500010
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
char str[N];
int n,cnt,ch[N][2];
int f[N],g[N],root;
void build(int &x)
{
x=++cnt;
int opt=str[cnt]-'0';
if(opt==0)return ;
if(opt==1)build(ch[x][1]);
if(opt==2)build(ch[x][1]),build(ch[x][2]);
}
int main()
{
scanf("%s",str+1);
n=strlen(str+1);
build(root);
for(int i=n;i>=1;i--)
{
f[i]=g[ch[i][1]]+g[ch[i][2]]+1;
g[i]=max(f[ch[i][1]]+g[ch[i][2]],f[ch[i][2]]+g[ch[i][1]]);
}
printf("%d ",max(f[1],g[1]));
for(int i=n;i>=1;i--)
{
f[i]=g[ch[i][1]]+g[ch[i][2]]+1;
g[i]=min(f[ch[i][1]]+g[ch[i][2]],f[ch[i][2]]+g[ch[i][1]]);
}
printf("%d",min(f[1],g[1]));
return 0;
}
```