[ZJOI2006]三色二叉树

BZOJ

luogu

分3种颜色讨论转移一下

#include<bits/stdc++.h>

using namespace std;

const int _=500005;

int n,now;

int ls[_],rs[_],r[_],g[_],b[_];

char s[_];

void bu(int u){

    if(s[u]=='1'||s[u]=='2'){++now;bu(ls[u]=now);}

    if(s[u]=='2'){++now;bu(rs[u]=now);}

}

void qmax(int u){

    if(s[u]=='0'){g[u]=1;r[u]=0;b[u]=0;return;}

    if(s[u]=='1'){

        int v=ls[u];qmax(v);

        g[u]=max(b[v],r[v])+1;

        r[u]=max(g[v],b[v]);

        b[u]=max(g[v],r[v]);

    }

    if(s[u]=='2'){

        qmax(ls[u]);qmax(rs[u]);

        g[u]=max(b[ls[u]]+r[rs[u]],r[ls[u]]+b[rs[u]])+1;

        b[u]=max(g[ls[u]]+r[rs[u]],r[ls[u]]+g[rs[u]]);

        r[u]=max(b[ls[u]]+g[rs[u]],g[ls[u]]+b[rs[u]]);

    }

}

void qmin(int u){

    if(s[u]=='0'){g[u]=1;r[u]=0;b[u]=0;return;}

    if(s[u]=='1'){

        int v=ls[u];qmin(v);

        g[u]=min(b[v],r[v])+1;

        r[u]=min(g[v],b[v]);

        b[u]=min(g[v],r[v]);

    }

    if(s[u]=='2'){

        qmin(ls[u]);qmin(rs[u]);

        g[u]=min(b[ls[u]]+r[rs[u]],r[ls[u]]+b[rs[u]])+1;

        b[u]=min(g[ls[u]]+r[rs[u]],r[ls[u]]+g[rs[u]]);

        r[u]=min(b[ls[u]]+g[rs[u]],g[ls[u]]+b[rs[u]]);

    }

}

int main(){

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

    bu(now=1);

    qmax(1);

    printf("%d ",max(g[1],max(r[1],b[1])));

    memset(g,63,sizeof(g));

    memset(r,63,sizeof(r));

    memset(b,63,sizeof(b));

    qmin(1);

    printf("%d\n",min(g[1],min(b[1],r[1])));

    return 0;

}