题意简述
给定一棵 \(n\) 个节点的二叉树，每个节点可以染成红、绿、蓝三种颜色中的一种。要求如果一个节点有一个子节点，那么它与子节点的颜色必须不同；如果一个节点有两个子节点，那么它们三个点的颜色必须两两不同，求染成绿色的点的个数的最小值和最大值。
\(n \leq 5\times 10^5\)。
Solution
因为最小值和最大值是对称的，所以这里只写最小值的做法。
设 \(f_{i,0/1/2}\) 表示节点 \(i\) 染成绿 \(/\) 红 \(/\) 蓝，以 \(i\) 为根的子树中最少要有多少个节点染成绿色。
- 若 \(i\) 只有一个孩子，设这个孩子为 \(son\)。
\[f_{i,0}=\min\{f_{son,1},f_{son,2}\}+1 \f_{i,1}=\min\{f_{son,0},f_{son,2}\} \f_{i,2}=\min\{f_{son,0},f_{son,1}\}
\]
- 若 \(i\) 有两个孩子，设这两个孩子分别为 \(ls,rs\)。
\[f_{i,0}=\min\{f_{ls,1}+f_{rs,2},f_{ls,2}+f_{rs,1}\} + 1 \f_{i,1}=\min\{f_{ls,0}+f_{rs,2},f_{ls,2}+f_{rs,0}\} \f_{i,2}=\min\{f_{ls,0}+f_{rs,1},f_{ls,1}+f_{rs,0}\}
\]
最大值的话就把 \(\min\) 换成 \(\max\) 即可。
代码如下：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
using namespace std;
inline int read() {
int num = 0 ,f = 1; char c = getchar();
while (!isdigit(c)) f = c == ‘-‘ ? -1 : f ,c = getchar();
while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
return num * f;
}
const int N = 5e5 + 5;
char str[N];
int f[3][N] ,g[3][N] ,cnt;
// f -> min ,g -> max
inline void dfs(int now) {
int soncnt = str[now] - ‘0‘;
f[0][now] = g[0][now] = 1;
if (soncnt == 0) return ;
else if (soncnt == 1) {
int son = ++cnt;
dfs(son);
f[0][now] += min(f[1][son] ,f[2][son]);
f[1][now] += min(f[0][son] ,f[2][son]);
f[2][now] += min(f[0][son] ,f[1][son]);
g[0][now] += max(g[1][son] ,g[2][son]);
g[1][now] += max(g[0][son] ,g[2][son]);
g[2][now] += max(g[0][son] ,g[1][son]);
}
else {
int ls = ++cnt;
dfs(ls);
int rs = ++cnt;
dfs(rs);
f[0][now] += min(f[1][ls] + f[2][rs] ,f[2][ls] + f[1][rs]);
f[1][now] += min(f[0][ls] + f[2][rs] ,f[2][ls] + f[0][rs]);
f[2][now] += min(f[0][ls] + f[1][rs] ,f[1][ls] + f[0][rs]);
g[0][now] += max(g[1][ls] + g[2][rs] ,g[2][ls] + g[1][rs]);
g[1][now] += max(g[0][ls] + g[2][rs] ,g[2][ls] + g[0][rs]);
g[2][now] += max(g[0][ls] + g[1][rs] ,g[1][ls] + g[0][rs]);
}
}
signed main() {
scanf("%s" ,str + 1);
dfs(++cnt);
printf("%d %d\n" ,max(g[0][1] ,max(g[1][1] ,g[2][1])) ,min(f[0][1] ,min(f[1][1] ,f[2][1])));
return 0;
}