洛谷P2585 [ZJOI2006]三色二叉树

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 500010

using namespace std;

struct node
{
    int lc,rc;
    int son;
};
node tree[maxn<<1];
char s[maxn];
int n,dp[maxn][2];
int f[maxn][2];
int siz_2[maxn],cnt;
bool vis[maxn];

inline void dfs(int now)
{
    if(now==-1) return;
    dfs(tree[now].lc);
    dfs(tree[now].rc);
    if(tree[now].son==2)
    {
        dp[now][0]=max(dp[tree[now].lc][1]+dp[tree[now].rc][0],dp[tree[now].lc][0]+dp[tree[now].rc][1]);
        //dp[now][0]=max(dp[tree[now].lc][0]+dp[tree[now].rc][0],dp[now][0]);
        dp[now][1]=dp[tree[now].lc][0]+dp[tree[now].rc][0];
        dp[now][1]+=1;
        f[now][0]=min(f[tree[now].lc][1]+f[tree[now].rc][0],f[tree[now].lc][0]+f[tree[now].rc][1]);
        //f[now][0]=min(f[tree[now].lc][0]+f[tree[now].rc][0],f[now][0]);
        f[now][1]=f[tree[now].lc][0]+f[tree[now].rc][0];
        f[now][1]+=1;
        if(f[now][0]==0) f[now][0]=1;
    }
    else if(tree[now].son==1)
    {
        dp[now][0]=max(dp[tree[now].lc][1],dp[tree[now].lc][0]);
        dp[now][1]=dp[tree[now].lc][0]+1;
        f[now][1]=f[tree[now].lc][0]+1;
        f[now][0]=min(f[tree[now].lc][1],f[tree[now].lc][0]);
    }
    else
    {
        dp[now][0]=0; dp[now][1]=1;
        f[now][0]=0; f[now][1]=1;
    }
    return;
}

inline void build()
{
    for(register int i=1;i<=n;++i)
    {
        if(s[i]-‘0‘==0)
        {
            tree[i].lc=-1;
            tree[i].rc=-1;
            tree[i].son=0;
        }
        else if(s[i]-‘0‘==1)
        {
            tree[i].lc=i+1;
            vis[i+1]=true;
            tree[i].rc=-1;
            tree[i].son=1;
        }
        else 
        {
            tree[i].son=2;
            tree[i].lc=i+1;
            vis[i+1]=true;
            if(!vis[i]) tree[siz_2[cnt--]].rc=i,vis[i]=true;
            siz_2[++cnt]=i;
        }
        if(!vis[i]) tree[siz_2[cnt--]].rc=i,vis[i]=true;
    }
    return;
} 

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    build();
    dfs(1);
    printf("%d %d",max(dp[1][1],dp[1][0]),min(f[1][1],f[1][0]));
    return 0;
}