1864: [Zjoi2006]三色二叉树

Time Limit: 1 Sec  Memory Limit: 64 MB

Submit: 773  Solved: 548

[][][]

Description

Input

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

Output

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

Sample Input

1122002010

Sample Output

5 2

HINT

 

Source

---

先建树

d[i][0/1]表示以i为根的子树i绿色1其他0下最多几个点绿色 

三个颜色转移就是父子三人两个其他一个绿色

见代码

/**************************************************************    Problem: 1864    User: thwfhk    Language: C++    Result: Accepted    Time:68 ms    Memory:13884 kb****************************************************************/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=5e5+5,INF=1e9;int n,mx=-INF,mn=INF;char s[N];struct node{    int ls,rs;    node():ls(0),rs(0){}}tree[N];int cnt=0,pos=1;int build(){    int u=++cnt,num=s[pos]-'0';    pos++;    if(num>=1) tree[u].ls=build();    if(num==2) tree[u].rs=build();    return u;}int d[N][2],f[N][2];void dp(int u){
    //printf("dp %d\n",u);    if(u==0) return;    int ls=tree[u].ls,rs=tree[u].rs;    dp(ls);dp(rs);    d[u][0]=max(d[ls][0]+d[rs][1],d[ls][1]+d[rs][0]);    f[u][0]=min(f[ls][0]+f[rs][1],f[ls][1]+f[rs][0]);    d[u][1]=d[ls][0]+d[rs][0]+1;    f[u][1]=f[ls][0]+f[rs][0]+1;}int main(int argc, const char * argv[]) {    scanf("%s",s+1);    n=strlen(s+1);    build();    dp(1);    mx=max(d[1][0],d[1][1]);    mn=min(f[1][0],f[1][1]);    printf("%d %d",mx,mn);    return 0;}