题目描述

Description

Input

仅有一行，不超过500000个字符，表示一个二叉树序列。

Output

输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

Sample Input

1122002010

Sample Output

5 2

题目分析

简单的树形DP
f[x]代表x是绿色时x的子树里最多/最少有多少点染成绿色
g[x]代表x不是绿色时x的子树里最多/最少有多少点染成绿色
递归进行DP max一遍 min一遍

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
char s[500100];
int l[500100],r[500100];
int f[500100],g[500100];
int p=-1,n;
void init()
{
    p++,n++;
    int now=n;
    if(s[p]=='2')
        l[now]=n+1,init(),r[now]=n+1,init();
    else if(s[p]=='1')
        l[now]=n+1,init();
}
void dpmax(int x)
{
    if(!x) return ;
    dpmax(l[x]),dpmax(r[x]);
    f[x]=g[l[x]]+g[r[x]]+1;
    g[x]=max(g[l[x]]+f[r[x]],f[l[x]]+g[r[x]]);
}
void dpmin(int x)
{
    if(!x) return ;
    dpmin(l[x]),dpmin(r[x]);
    f[x]=g[l[x]]+g[r[x]]+1;
    g[x]=min(g[l[x]]+f[r[x]],f[l[x]]+g[r[x]]);;
}
int main()
{
    scanf("%s",&s[0]);
    init();
    dpmax(1);
    printf("%d ",max(f[1],g[1]));
    memset(f,0,sizeof f);
    memset(g,0,sizeof g);
    dpmin(1);
    printf("%d",min(f[1],g[1]));
    return 0;
}