1 /************************************************************** 2     Problem: 1864 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:24 ms 7     Memory:19244 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12   13 #define Rep(i, n) for (i = 0; i < n; ++i)14 using namespace std;15 const int inf = (int) 1e9;16 const int N = 500005;17   18 int cnt, s[N][3], f[N][3], g[N][3];19   20 void dfs(int p) {21     int i, j, k;22     s[p][0] = getchar() - ‘0‘;23     if (!s[p][0]) {24         f[p][0] = g[p][0] = 1;25         return;26     }27     for (i = 1; i <= s[p][0]; ++i) {28         s[p][i] = ++cnt;29         dfs(cnt);30     }31     g[p][0] = g[p][1] = g[p][2] = inf;32     if (s[p][0] == 1) {33         Rep(i, 3) Rep(j, 3)34             if (i != j)35                 f[p][i] = max(f[p][i], f[s[p][1]][j] + !i),36                 g[p][i] = min(g[p][i], g[s[p][1]][j] + !i);37     } else {38         Rep(i, 3) Rep(j, 3) Rep(k, 3)39             if (i != j && j != k && i != k)40                 f[p][i] = max(f[p][i], f[s[p][1]][j] + f[s[p][2]][k] + !i),41                 g[p][i] = min(g[p][i], g[s[p][1]][j] + g[s[p][2]][k] + !i);42     }43 }44   45 int main() {46     dfs(cnt = 1);47     printf("%d %d\n", max(max(f[1][0], f[1][1]), f[1][2]), min(min(g[1][0], g[1][1]), g[1][2]));48     return 0;49 }