Luogu P2585 [ZJOI2006]三色二叉树 题解

#include<bits/stdc++.h>
using namespace std;
char str[500010];
int f[500010][3],g[500010][3],tot;
inline void DFS(int x){
    if(str[x]=='0'){
        f[x][0]=g[x][0]=1;
        return ;
    }else if(str[x]=='1'){
        int son=x+1;
        DFS(++tot);
        f[x][0]=max(f[son][1],f[son][2])+1;
        f[x][1]=max(f[son][0],f[son][2]);
        f[x][2]=max(f[son][0],f[son][1]);
        g[x][0]=min(g[son][1],g[son][2])+1;//最小值
        g[x][1]=min(g[son][0],g[son][2]);
        g[x][2]=min(g[son][0],g[son][1]);
    }else if(str[x]=='2'){
        int l=x+1;DFS(++tot);
        int r=tot+1;DFS(++tot);
        f[x][0]=max(f[l][1]+f[r][2],f[l][2]+f[r][1])+1;
        f[x][1]=max(f[l][0]+f[r][2],f[l][2]+f[r][0]);
        f[x][2]=max(f[l][0]+f[r][1],f[l][1]+f[r][0]);
        g[x][0]=min(g[l][1]+g[r][2],g[l][2]+g[r][1])+1;//最小值
        g[x][1]=min(g[l][0]+g[r][2],g[l][2]+g[r][0]);
        g[x][2]=min(g[l][0]+g[r][1],g[l][1]+g[r][0]);
    }
}
int main(){
    cin>>str+1;
    DFS(++tot);
    cout<<max(f[1][0],max(f[1][1],f[1][2]))<<" "<<min(g[1][0],min(g[1][1],g[1][2]))<<endl;
}