【BZOJ】1864: [Zjoi2006]三色二叉树

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 char s[500005];
 7 int now, len;
 8 
 9 int dp1[1000005][3], dp2[1000005][3], son[1000005][3];
10 int MA, MI;
11 
12 int stot, tov[2000005], nex[2000005], h[1000005];
13 
14 void add ( int u, int v ) {
15     tov[++stot] = v;
16     nex[stot] = h[u];
17     h[u] = stot;
18 }
19 
20 void build ( int pos, int f ) {
21     add ( f, pos ); add ( pos, f );
22     if ( s[pos-1] == ‘0‘ ) {
23         now = pos;
24         return ;
25     }
26     if ( s[pos-1] == ‘1‘ ) {
27         build ( pos + 1, pos );
28     }
29     if ( s[pos-1] == ‘2‘ ) {
30         build ( pos + 1, pos );
31         build ( now + 1, pos );
32     }
33 }
34 
35 void dfs ( int u, int f ) {
36     for ( int i = h[u]; i; i = nex[i] ) {
37         int v = tov[i];
38         if ( v == f ) continue;
39         dfs ( v, u );
40         son[u][son[u][2]++] = v;
41     }
42     int l = son[u][0], r = son[u][1];
43     if ( son[u][2] == 1 ) {
44         dp1[u][0] = max ( dp1[l][1], dp1[l][2] );
45         dp1[u][1] = max ( dp1[l][0], dp1[l][2] );
46         dp1[u][2] = max ( dp1[l][1], dp1[l][0] ) + 1;
47         dp2[u][0] = min ( dp2[l][1], dp2[l][2] );
48         dp2[u][1] = min ( dp2[l][0], dp2[l][2] );
49         dp2[u][2] = min ( dp2[l][1], dp2[l][0] ) + 1;
50     } else if ( son[u][2] == 2 ){
51         dp1[u][0] = max ( dp1[l][1] + dp1[r][2], dp1[r][1] + dp1[l][2] );
52         dp1[u][1] = max ( dp1[l][0] + dp1[r][2], dp1[r][0] + dp1[l][2] );
53         dp1[u][2] = max ( dp1[l][1] + dp1[r][0], dp1[r][1] + dp1[l][0] ) + 1;
54         dp2[u][0] = min ( dp2[l][1] + dp2[r][2], dp2[r][1] + dp2[l][2] );
55         dp2[u][1] = min ( dp2[l][0] + dp2[r][2], dp2[r][0] + dp2[l][2] );
56         dp2[u][2] = min ( dp2[l][1] + dp2[r][0], dp2[r][1] + dp2[l][0] ) + 1;
57     } else {
58         dp1[u][0] = dp1[u][1] = 0;
59         dp1[u][2] = 1;
60         dp2[u][0] = dp2[u][1] = 0;
61         dp2[u][2] = 1;
62     }
63 }
64 
65 int main ( ) {
66     cin >> s;
67     len = strlen ( s );
68     build ( 1, 0 );
69     dfs ( 1, 0 );
70     MA = max ( dp1[1][0], max ( dp1[1][1], dp1[1][2] ) );
71     MI = min ( dp2[1][0], min ( dp2[1][1], dp2[1][2] ) );
72     printf ( "%d %d", MA, MI );
73 }