题目
题目链接
题目大意：给出一颗 $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;
}
|