题目大意：给定一个二叉树，可以染红绿黄三种颜色，要求父节点和子节点的颜色不同，且如果一个节点有两个子节点，那么两个子节点之间的颜色也不同。求最多和最少有多少个节点会被染成绿色。

题解：加深了对二叉树的理解。

对于二叉树来说，每个节点只需保留左右儿子节点编号即可。设 \(f[i]\) 表示以 i 为根的子树且 i 是绿色的绿色节点个数，\(g[i]\) 表示以 i 为根的子树，且 i 不是绿色的绿色节点个数，每次对于 \(g[i]\) 有两种决策，取相应的最优值即可。

代码如下

#include <bits/stdc++.h>

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define all(x) x.begin(),x.end()

#define cls(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int dx[]={0,1,0,-1};

const int dy[]={1,0,-1,0};

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

const int maxn=5e5+10;

const double eps=1e-6;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll sqr(ll x){return x*x;}

inline ll fpow(ll a,ll b,ll c){ll ret=1%c;for(;b;b>>=1,a=a*a%c)if(b&1)ret=ret*a%c;return ret;}

inline ll read(){

    ll x=0,f=1;char ch;

    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

    do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

    return f*x;

}

/*------------------------------------------------------------*/

char s[maxn];int idx;

int n,l[maxn],r[maxn],ansmx,ansmi;

int f[maxn],g[maxn];

void get(int now){

    ++idx;

    if(s[now]=='0')return;

    else if(s[now]=='1')l[now]=idx+1,get(idx+1);

    else{

        l[now]=idx+1,get(idx+1);

        r[now]=idx+1,get(idx+1);

    }

}

void read_and_parse(){

    scanf("%s",s+1),n=strlen(s+1);

    get(1);

}

void mx(int u){

    if(!u)return;

    mx(l[u]),mx(r[u]);

    f[u]=g[l[u]]+g[r[u]]+1;

    g[u]=max(g[l[u]]+f[r[u]],f[l[u]]+g[r[u]]);

}

void mi(int u){

    if(!u)return;

    mi(l[u]),mi(r[u]);

    f[u]=g[l[u]]+g[r[u]]+1;

    g[u]=min(g[l[u]]+f[r[u]],f[l[u]]+g[r[u]]);

}

void solve(){

    mx(1);

    ansmx=max(f[1],g[1]);

    cls(f,0),cls(g,0);

    mi(1);

    ansmi=min(f[1],g[1]);

    printf("%d %d\n",ansmx,ansmi);

}

int main(){

    read_and_parse();

    solve();

    return 0;

}