0%

[ZJOI2006] 三色二叉树

题目

题目链接

题目大意:给出一颗 $n$ 个结点的二叉树,每个结点可以染成红色,绿色或蓝色,每个结点和相邻的结点颜色必须不同,同一个结点的子结点颜色也必须不同,问最多和最少有多少个点能被染成绿色。$1 \le n \le 5 \times 10^5$。

思路

首先这个树的输入十分不一样,用了个序列来表示。

设 $f(i, 0/1/2)$ 表示第 $i$ 个点染成绿色,红色或蓝色时最大方案数,那么有 $f(i, 0) = \max(f(l, 1) + f(r, 2), f(l, 2) + f(r, 1)) + 1$,其中 $l, r$ 是 $i$ 的左右结点。

同理,有

$$
f(i, 1) = \max(f(l, 0) + f(r, 2) + f(l, 2) + f(r, 0))
$$
$$
f(i, 2) = \max(f(l, 0) + f(r, 1) + f(l, 1) + f(r, 0))
$$

最小值同理。

代码

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
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

int f[500010][4], g[500010][4];
int cnt = 1;
char s[500010];

void dfs(int x) {
if (s[x] == '0') {
f[x][0] = g[x][0] = 1;
return ;
}
dfs(++cnt);
if (s[x] == '1') {
f[x][0] = std::max(f[x + 1][1], f[x + 1][2]) + 1;
f[x][1] = std::max(f[x + 1][0], f[x + 1][2]);
f[x][2] = std::max(f[x + 1][0], f[x + 1][1]);
g[x][0] = std::min(g[x + 1][1], g[x + 1][2]) + 1;
g[x][1] = std::min(g[x + 1][0], g[x + 1][2]);
g[x][2] = std::min(g[x + 1][0], g[x + 1][1]);
} else {
int k = ++cnt;
dfs(cnt);
f[x][0] = std::max(f[x + 1][1] + f[k][2], f[x + 1][2] + f[k][1]) + 1;
f[x][1] = std::max(f[x + 1][0] + f[k][2], f[x + 1][2] + f[k][0]);
f[x][2] = std::max(f[x + 1][0] + f[k][1], f[x + 1][1] + f[k][0]);
g[x][0] = std::min(g[x + 1][1] + g[k][2], g[x + 1][2] + g[k][1]) + 1;
g[x][1] = std::min(g[x + 1][0] + g[k][2], g[x + 1][2] + g[k][0]);
g[x][2] = std::min(g[x + 1][0] + g[k][1], g[x + 1][1] + g[k][0]);
}
}

int main() {
scanf("%s", s + 1);
dfs(1);
printf("%d %d\n", f[1][0], std::min(g[1][0], std::min(g[1][1], g[1][2])));
return 0;
}