[ZJOI 2006] 三色二叉树

题目大意

对一个二叉树的节点进行红、绿、蓝的染色，父子节点、兄弟节点之间不同色。求最多／少能染多少个绿色节点。

二叉树的给出方式为一个只由 $0$、$1$、$2$ 组成的数字序列。若为 $0$ ，表示叶子节点；若为 $1$，表示有一个子节点，之后的序列描述这个节点的子树；若为 $2$，表示有两个子节点，之后的序列描述子树。

$1 \leqslant n \leqslant 500,000$

题目链接

【ZJOI 2006】三色二叉树 - Luogu 2585

题解

树形 DP。

不用管不是绿色的节点是红色还是蓝色。

记 $f[u, \; 0/1]$ 表示节点 $u$ 在不是／是绿色时子树的答案，转移为（以最大值为例）：

\begin{align} f[u, \; 1] &= f[u.lc, \; 0] + f[u.rc, \; 0] + 1 \\ f[u, \; 0] &= max(f[u.lc, \; 0] + f[u.rc, \; 1], \; f[u.lc, \; 1] + f[u.rc, \; 0]) \end{align}

最小值同理。

代码

节点和边根本不记录多少东西，就不用结构体了。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 500005;
int f[MAXN][2];
int l[MAXN], r[MAXN];
void readTree(int u = 1) {
    static int nodeIndex = 1;
    char ch = getchar();
    if (ch == '0') return;
    l[u] = ++nodeIndex;
    readTree(nodeIndex);
    if (ch == '2') {
        r[u] = ++nodeIndex;
        readTree(nodeIndex);
    }
}
void dpMax(int u = 1) {
    if (u == 0) return;
    dpMax(l[u]);
    dpMax(r[u]);
    f[u][1] = f[l[u]][0] + f[r[u]][0] + 1;
    f[u][0] = std::max(f[l[u]][1] + f[r[u]][0], f[l[u]][0] + f[r[u]][1]);
}
void dpMin(int u = 1) {
    if (u == 0) return;
    dpMin(l[u]);
    dpMin(r[u]);
    f[u][1] = f[l[u]][0] + f[r[u]][0] + 1;
    f[u][0] = std::min(f[l[u]][1] + f[r[u]][0], f[l[u]][0] + f[r[u]][1]);
}
int main() {
    readTree();
    dpMax();
    int ansMax = std::max(f[1][1], f[1][0]);
    memset(f, 0, sizeof (f));
    dpMin();
    int ansMin = std::min(f[1][1], f[1][0]);
    printf("%d %d\n", ansMax, ansMin);
    return 0;
}