题解 P2585 【[ZJOI2006]三色二叉树】

在此给出一个相对较简的实现

人话题意：递归地给出一棵二叉树，节点的颜色可以是0,1,2，父子节点、兄弟节点间的颜色不同，求最多（最少）可以有多少个点为0色。

朴素的树形dp，读入数据是比较麻烦的。

可以发现实际上只有绿和不为绿两种状态，最大/最小做两遍即可，在此以最大为例：

以 f_{i} 表示点 i 为绿色时最多有多少点可以为绿，g_{i} 表示点 i 不为绿色时最多多少点可以为绿。

转移是这样的，设当前节点为 i ，若为绿色，则子节点必须非绿。若不为绿色，则从两个儿子分别一绿一不绿的状态取 max 转移而来。

代码如下：

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