[ZJOI 2006] 三色二叉树

题目大意

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

二叉树的给出方式为一个只由 001122 组成的数字序列。若为 00 ,表示叶子节点;若为 11,表示有一个子节点,之后的序列描述这个节点的子树;若为 22,表示有两个子节点,之后的序列描述子树。

1n500,0001 \leqslant n \leqslant 500,000

题目链接

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

题解

树形 DP。

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

f[u,  0/1]f[u, \; 0/1] 表示节点 uu 在不是/是绿色时子树的答案,转移为(以最大值为例):

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

最小值同理。

代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}