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

(Updated: )
oi

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}