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

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

Describe

题目链接

Solution

0-绿色，1-红色，2-蓝色。 设f[i][j]表示i节点染成j这种颜色的最大值。 如果i节点的没有儿子，那么很明显f[i][0]=1。 如果i节点有一个儿子，那么f[i][0]=max(f[to][1],f[to][2]) 1,f[i][1]=max(f[to][0],f[to][2])（颜色染成蓝色与红色类似） 如果i节点有两个儿子，那么f[i][0]=max(f[lson][1] f[rson][2],f[lson][2] f[rson][1]) 1（颜色染成红色、蓝色只需不用-1即可） 最大值如此，最小值类似。

Code

代码语言：javascript复制

#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;
} 

二叉树 max ode

0 人点赞