P2585 [ZJOI2006]三色二叉树

· · 个人记录

题目在这里

思路

经典的树上DP，做起来十分丝滑。建树的话直接模拟一遍即可。 然后想到dp[i][j][k]表示第i个点涂色j时子树中颜色k的最大（最小）值。 然后随便暴力枚举每种涂色DP即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int now,cnt,l[N],r[N],dp[N][4][4],f[N][4][4];//第i个点染x色，y色最大值。
char c[N]; 
void dfs(int u){
    if(c[now]=='2'){
        now++,l[u]=++cnt,dfs(cnt);
        now++,r[u]=++cnt,dfs(cnt);
    }
    else if(c[now]=='1')
        now++,l[u]=++cnt,dfs(cnt);
    return;
}
void print(int u){
    cout<<u<<l[u]<<r[u]<<endl;
    if(l[u])print(l[u]);
    if(r[u])print(r[u]);
    return;
}
void work2(int u){
    if(l[u] && r[u]){
        work2(l[u]),work2(r[u]);
        f[u][1][1]=min(f[l[u]][2][1]+f[r[u]][3][1],f[l[u]][3][1]+f[r[u]][2][1])+1;
        f[u][2][1]=min(f[l[u]][1][1]+f[r[u]][3][1],f[l[u]][3][1]+f[r[u]][1][1]);
        f[u][3][1]=min(f[l[u]][1][1]+f[r[u]][2][1],f[l[u]][2][1]+f[r[u]][1][1]);

        f[u][1][2]=min(f[l[u]][2][2]+f[r[u]][3][2],f[l[u]][3][2]+f[r[u]][2][2]);
        f[u][2][2]=min(f[l[u]][1][2]+f[r[u]][3][2],f[l[u]][3][2]+f[r[u]][1][2])+1;
        f[u][3][2]=min(f[l[u]][1][2]+f[r[u]][2][2],f[l[u]][2][2]+f[r[u]][1][2]);

        f[u][1][3]=min(f[l[u]][2][3]+f[r[u]][3][3],f[l[u]][3][3]+f[r[u]][2][3]);
        f[u][2][3]=min(f[l[u]][1][3]+f[r[u]][3][3],f[l[u]][3][3]+f[r[u]][1][3]);
        f[u][3][3]=min(f[l[u]][1][3]+f[r[u]][2][3],f[l[u]][2][3]+f[r[u]][1][3])+1;
    }
    else if(l[u]){
        work2(l[u]);
        f[u][1][1]=min(f[l[u]][2][1],f[l[u]][3][1])+1;
        f[u][2][1]=min(f[l[u]][1][1],f[l[u]][3][1]);
        f[u][3][1]=min(f[l[u]][2][1],f[l[u]][1][1]);

        f[u][1][2]=min(f[l[u]][2][2],f[l[u]][3][2]);
        f[u][2][2]=min(f[l[u]][1][2],f[l[u]][3][2])+1;
        f[u][3][2]=min(f[l[u]][2][2],f[l[u]][1][2]);

        f[u][1][3]=min(f[l[u]][2][3],f[l[u]][3][3]);
        f[u][2][3]=min(f[l[u]][1][3],f[l[u]][3][3]);
        f[u][3][3]=min(f[l[u]][2][3],f[l[u]][1][3])+1;
    }
    else{
        f[u][1][1]=1;
        f[u][2][2]=1;
        f[u][3][3]=1;
    }
    return;
}
void work(int u){
    if(l[u] && r[u]){
        work(l[u]),work(r[u]);
        dp[u][1][1]=max(dp[l[u]][2][1]+dp[r[u]][3][1],dp[l[u]][3][1]+dp[r[u]][2][1])+1;
        dp[u][2][1]=max(dp[l[u]][1][1]+dp[r[u]][3][1],dp[l[u]][3][1]+dp[r[u]][1][1]);
        dp[u][3][1]=max(dp[l[u]][1][1]+dp[r[u]][2][1],dp[l[u]][2][1]+dp[r[u]][1][1]);

        dp[u][1][2]=max(dp[l[u]][2][2]+dp[r[u]][3][2],dp[l[u]][3][2]+dp[r[u]][2][2]);
        dp[u][2][2]=max(dp[l[u]][1][2]+dp[r[u]][3][2],dp[l[u]][3][2]+dp[r[u]][1][2])+1;
        dp[u][3][2]=max(dp[l[u]][1][2]+dp[r[u]][2][2],dp[l[u]][2][2]+dp[r[u]][1][2]);

        dp[u][1][3]=max(dp[l[u]][2][3]+dp[r[u]][3][3],dp[l[u]][3][3]+dp[r[u]][2][3]);
        dp[u][2][3]=max(dp[l[u]][1][3]+dp[r[u]][3][3],dp[l[u]][3][3]+dp[r[u]][1][3]);
        dp[u][3][3]=max(dp[l[u]][1][3]+dp[r[u]][2][3],dp[l[u]][2][3]+dp[r[u]][1][3])+1;
    }
    else if(l[u]){
        work(l[u]);
        dp[u][1][1]=max(dp[l[u]][2][1],dp[l[u]][3][1])+1;
        dp[u][2][1]=max(dp[l[u]][1][1],dp[l[u]][3][1]);
        dp[u][3][1]=max(dp[l[u]][2][1],dp[l[u]][1][1]);

        dp[u][1][2]=max(dp[l[u]][2][2],dp[l[u]][3][2]);
        dp[u][2][2]=max(dp[l[u]][1][2],dp[l[u]][3][2])+1;
        dp[u][3][2]=max(dp[l[u]][2][2],dp[l[u]][1][2]);

        dp[u][1][3]=max(dp[l[u]][2][3],dp[l[u]][3][3]);
        dp[u][2][3]=max(dp[l[u]][1][3],dp[l[u]][3][3]);
        dp[u][3][3]=max(dp[l[u]][2][3],dp[l[u]][1][3])+1;
    }
    else{
        dp[u][1][1]=1;
        dp[u][2][2]=1;
        dp[u][3][3]=1;
    }
    return;
}
int main(){
    cin>>c+1;now=1;
    dfs(++cnt);
    work(1);
    int maxn=0,minn=1e9;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            maxn=max(maxn,dp[1][i][j]);
    }
    work2(1);
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            minn=min(minn,f[1][i][j]);
    }

    printf("%d %d\n",maxn,minn);
    return 0;
}