1864: [Zjoi2006]三色二叉树

Time Limit: 1 Sec  Memory Limit: 64 MB

Submit: 1295  Solved: 961

[][][]

Description

                                                 

Input

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

Output

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

Sample Input

1122002010

Sample Output

5 2

HINT

 

Source

[ ][ ][ ]

 Back

 

其实是一道基础的树规辣~一开始觉得难点可能在建边上，可是建边也很好搞是怎么肥四？？（其实就是一道水题

建了边直接dfs往上dp就可以辣！

 

#include
     
      #include
      
       #include
       
        using namespace std;char s[500005];int now, len;int dp1[1000005][3], dp2[1000005][3], son[1000005][3];int MA, MI;int stot, tov[2000005], nex[2000005], h[1000005];void add ( int u, int v ) {    tov[++stot] = v;    nex[stot] = h[u];    h[u] = stot;}void build ( int pos, int f ) {    add ( f, pos ); add ( pos, f );    if ( s[pos-1] == '0' ) {        now = pos;        return ;    }    if ( s[pos-1] == '1' ) {        build ( pos + 1, pos );    }    if ( s[pos-1] == '2' ) {        build ( pos + 1, pos );        build ( now + 1, pos );    }}void dfs ( int u, int f ) {    for ( int i = h[u]; i; i = nex[i] ) {        int v = tov[i];        if ( v == f ) continue;        dfs ( v, u );        son[u][son[u][2]++] = v;    }    int l = son[u][0], r = son[u][1];    if ( son[u][2] == 1 ) {        dp1[u][0] = max ( dp1[l][1], dp1[l][2] );        dp1[u][1] = max ( dp1[l][0], dp1[l][2] );        dp1[u][2] = max ( dp1[l][1], dp1[l][0] ) + 1;        dp2[u][0] = min ( dp2[l][1], dp2[l][2] );        dp2[u][1] = min ( dp2[l][0], dp2[l][2] );        dp2[u][2] = min ( dp2[l][1], dp2[l][0] ) + 1;    } else if ( son[u][2] == 2 ){        dp1[u][0] = max ( dp1[l][1] + dp1[r][2], dp1[r][1] + dp1[l][2] );        dp1[u][1] = max ( dp1[l][0] + dp1[r][2], dp1[r][0] + dp1[l][2] );        dp1[u][2] = max ( dp1[l][1] + dp1[r][0], dp1[r][1] + dp1[l][0] ) + 1;        dp2[u][0] = min ( dp2[l][1] + dp2[r][2], dp2[r][1] + dp2[l][2] );        dp2[u][1] = min ( dp2[l][0] + dp2[r][2], dp2[r][0] + dp2[l][2] );        dp2[u][2] = min ( dp2[l][1] + dp2[r][0], dp2[r][1] + dp2[l][0] ) + 1;    } else {        dp1[u][0] = dp1[u][1] = 0;        dp1[u][2] = 1;        dp2[u][0] = dp2[u][1] = 0;        dp2[u][2] = 1;    }}int main ( ) {    cin >> s;    len = strlen ( s );    build ( 1, 0 );    dfs ( 1, 0 );    MA = max ( dp1[1][0], max ( dp1[1][1], dp1[1][2] ) );    MI = min ( dp2[1][0], min ( dp2[1][1], dp2[1][2] ) );    printf ( "%d %d", MA, MI );}