题目
难得自己独立想出来并一次过的题目！！！后来翻了下题解自己似乎写复杂了（）
首先，染绿色这东西不用管，只要用三种颜色然后最后让最大或最小的那个颜色是绿色即可。
一看题，这递归建树挺 ex 的。定义 $f[0/1/2][x]$ 表示 $x$ 子树内的颜色 $0/1/2$ 的数量。转移了一下，发现不行。
再加一维，$f[0/1/2][0/1/2][x]$ 第一维表示 $x$ 点染的颜色，第二维表示统计 $x$ 子树内的哪种颜色。大力转移即可。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#define ll long long
using namespace std;
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
ll lrd() {
ll f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
#define int ll
#define max(A,B) (A>B?A:B)
#define min(A,B) (A>B?B:A)
const int N=(int)(5e5+5);
struct edge {
int nex,to;
}e[N<<1];
char str[N];
int head[N],cnt,tot,n,f[3][3][N]; //第一维它自己染什么颜色
void add_edge(int x,int y) {
e[++cnt].nex=head[x]; e[cnt].to=y; head[x]=cnt;
}
void init(int x) {
if(str[x]=='0'||x>n) return ;
if(str[x]=='2') {
int pre=tot;
add_edge(tot,tot+1),add_edge(tot+1,tot),++tot;
init(x+1); add_edge(pre,tot+1),add_edge(tot+1,pre),++tot;
init(x+tot-pre);
} else {
add_edge(tot,tot+1); add_edge(tot+1,tot); ++tot; init(x+1);
}
}
void dfs1(int x,int ff) {
int num=0; //cout<<x<<" "<<ff<<endl;
for(int i=head[x];i;i=e[i].nex) {
int y=e[i].to; if(y==ff) continue;
dfs1(y,x); ++num;
}
if(!num) {
f[0][0][x]=f[1][1][x]=f[2][2][x]=1;
} else if(num==1) {
for(int i=head[x];i;i=e[i].nex) {
int y=e[i].to; if(y==ff) continue;
f[0][0][x]+=1+max(f[1][0][y],f[2][0][y]);
f[0][1][x]+=max(f[1][1][y],f[2][1][y]);
f[0][2][x]+=max(f[1][2][y],f[2][2][y]);
f[1][0][x]+=max(f[0][0][y],f[2][0][y]);
f[1][1][x]+=1+max(f[0][1][y],f[2][1][y]);
f[1][2][x]+=max(f[0][2][y],f[2][2][y]);
f[2][0][x]+=max(f[0][0][y],f[1][0][y]);
f[2][1][x]+=max(f[0][1][y],f[1][1][y]);
f[2][2][x]+=1+max(f[0][2][y],f[1][2][y]);
}
} else {
int ls=0,rs;
for(int i=head[x];i;i=e[i].nex) {
int y=e[i].to; if(y==ff) continue;
if(!ls) ls=y; else rs=y;
}
f[0][0][x]+=1+max(f[1][0][ls]+f[2][0][rs],f[1][0][rs]+f[2][0][ls]);
f[0][1][x]+=max(f[1][1][ls]+f[2][1][rs],f[1][1][rs]+f[2][1][ls]);
f[0][2][x]+=max(f[1][2][ls]+f[2][2][rs],f[1][2][rs]+f[2][2][ls]);
f[1][0][x]+=max(f[0][0][ls]+f[2][0][rs],f[0][0][rs]+f[2][0][ls]);
f[1][1][x]+=1+max(f[0][1][ls]+f[2][1][rs],f[0][1][rs]+f[2][1][ls]);
f[1][2][x]+=max(f[0][2][ls]+f[2][2][rs],f[0][2][rs]+f[2][2][ls]);
f[2][0][x]+=max(f[0][0][ls]+f[1][0][rs],f[0][0][rs]+f[1][0][ls]);
f[2][1][x]+=max(f[0][1][ls]+f[1][1][rs],f[0][1][rs]+f[1][1][ls]);
f[2][2][x]+=1+max(f[0][2][ls]+f[1][2][rs],f[0][2][rs]+f[1][2][ls]);
}
}
void dfs2(int x,int ff) {
int num=0; //cout<<x<<" "<<ff<<endl;
for(int i=head[x];i;i=e[i].nex) {
int y=e[i].to; if(y==ff) continue;
dfs2(y,x); ++num;
}
if(!num) {
for(int i=0;i<3;i++) for(int j=0;j<3;j++) f[i][j][x]=0;
f[0][0][x]=f[1][1][x]=f[2][2][x]=1;
} else if(num==1) {
for(int i=head[x];i;i=e[i].nex) {
int y=e[i].to; if(y==ff) continue;
f[0][0][x]+=1+min(f[1][0][y],f[2][0][y]);
f[0][1][x]+=min(f[1][1][y],f[2][1][y]);
f[0][2][x]+=min(f[1][2][y],f[2][2][y]);
f[1][0][x]+=min(f[0][0][y],f[2][0][y]);
f[1][1][x]+=1+min(f[0][1][y],f[2][1][y]);
f[1][2][x]+=min(f[0][2][y],f[2][2][y]);
f[2][0][x]+=min(f[0][0][y],f[1][0][y]);
f[2][1][x]+=min(f[0][1][y],f[1][1][y]);
f[2][2][x]+=1+min(f[0][2][y],f[1][2][y]);
}
} else {
int ls=0,rs;
for(int i=head[x];i;i=e[i].nex) {
int y=e[i].to; if(y==ff) continue;
if(!ls) ls=y; else rs=y;
}
f[0][0][x]+=1+min(f[1][0][ls]+f[2][0][rs],f[1][0][rs]+f[2][0][ls]);
f[0][1][x]+=min(f[1][1][ls]+f[2][1][rs],f[1][1][rs]+f[2][1][ls]);
f[0][2][x]+=min(f[1][2][ls]+f[2][2][rs],f[1][2][rs]+f[2][2][ls]);
f[1][0][x]+=min(f[0][0][ls]+f[2][0][rs],f[0][0][rs]+f[2][0][ls]);
f[1][1][x]+=1+min(f[0][1][ls]+f[2][1][rs],f[0][1][rs]+f[2][1][ls]);
f[1][2][x]+=min(f[0][2][ls]+f[2][2][rs],f[0][2][rs]+f[2][2][ls]);
f[2][0][x]+=min(f[0][0][ls]+f[1][0][rs],f[0][0][rs]+f[1][0][ls]);
f[2][1][x]+=min(f[0][1][ls]+f[1][1][rs],f[0][1][rs]+f[1][1][ls]);
f[2][2][x]+=1+min(f[0][2][ls]+f[1][2][rs],f[0][2][rs]+f[1][2][ls]);
}
}
signed main() {
scanf("%s",str+1); n=strlen(str+1);
tot=1; init(1);
dfs1(1,0); int ans1=0,ans2=2e18; for(int i=0;i<3;i++) for(int j=0;j<3;j++) ans1=max(ans1,f[i][j][1]);
memset(f,0,sizeof(f));
dfs2(1,0); for(int i=0;i<3;i++) for(int j=0;j<3;j++) ans2=min(ans2,f[i][j][1]);
printf("%lld %lld",ans1,ans2); return 0;
}