Luogu P2585 [ZJOI2006]三色二叉树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
char s[A];
int ch[A][2], cnt, rt, f[A][2], g[A][2];
void init(int &now) {
  now = ++cnt;
  int x = s[cnt] - '0';
  if (x == 0) return;
  else if (x == 1) init(ch[now][1]);
  else if (x == 2) init(ch[now][0]), init(ch[now][1]);
}
int maxx(int ifg, int son) {
  if (son == 0) return 0;
  if (~f[son][ifg]) return f[son][ifg];
  if (ifg) return f[son][ifg] = maxx(!ifg, ch[son][0]) + maxx(!ifg, ch[son][1]) + 1;
  else return f[son][ifg] = max(maxx(!ifg, ch[son][0]) + maxx(ifg, ch[son][1]), maxx(ifg, ch[son][0]) + maxx(!ifg, ch[son][1]));
}
int minn(int ifg, int son) {
  if (son == 0) return 0;
  if (~g[son][ifg]) return g[son][ifg];
  if (ifg) return g[son][ifg] = minn(!ifg, ch[son][0]) + minn(!ifg, ch[son][1]) + 1;
  else return g[son][ifg] = min(minn(!ifg, ch[son][0]) + minn(ifg, ch[son][1]), minn(ifg, ch[son][0]) + minn(!ifg, ch[son][1]));
}

int main(int argc, char const *argv[]) {
  cin >> (s + 1); init(rt); memset(f, -1, sizeof f); memset(g, -1, sizeof g);
  cout << max(maxx(0, 1), maxx(1, 1)) << " " << min(minn(0, 1), minn(1, 1)) << endl;
}