Codeforces Round 831 (Div. 1 + Div. 2) - E. Hanging Hearts (1800)

E. Hanging Hearts

Leaf 노드부터 올라가는 경로에 있다고 해보자.

어떤 노드 $u$와 그것의 부모 $p$가 있다고 하자.

$u$를 LIS의 원소로 취했다고 하자.

Longest Non-decreasing Sequence긴한데 그냥 본문에선 LIS라고 표기한다.

$p$도 LIS의 원소로 취하려면 항상 LIS에서 $u$와 $p$가 가지는 수가 같아야 한다.

그리고 $p$의 $u$를 제외한 모든 다른 자식들은 취할수가 없다.

취할수가 있다고 하자. $u$쪽의 서브트리에서 $u$가 LIS에서 가지는 값을 $x$라고 하면

다른 자식이 $x$보다 큰 LIS에서의 값을 가지면 $p$의 LIS에서의 값도 $x$가 되어야 해서 $p$를 LIS에 포함한다는 것이 불가능하고,

$x$보다 작은 값이라면 $p$의 LIS에서의 값이 $x$가 아닌 그 값이 되어야 하기 때문에 모순이다.

따라서 $p$를 LIS에 포함시키려면 $p$의 자식들 중 LIS에 자기 자신이 포함되는 자식의 결과중 가장 큰 것에 $+1$ 한 것이 최댓값이다.

반대로 $p$를 LIS에 포함시키지 않으려면 자식들 중 자기 자신이 포함되거나 말거나 두 경우중 큰 값을 모두 더해주면 된다.

즉, 그냥 Tree DP 문제이다.

void solve() {
   int n;
   cin >> n;
   vi p(n, -1);
   vvi edges(n);
   for (int i = 1; i < n; i++) {
      cin >> p[i];
      p[i]--;
      edges[p[i]].pb(i);
   }
   vvi dp(n, vi(2, -1));
   int ans = 0;
   function<int(int, int)> fn = [&](int cur, int with) -> int {
      if (!sz(edges[cur])) return with;
      int &ret = dp[cur][with];
      if (~ret) return ret;
 
      int inc_mx = 0, sum = 0;
      for (int to: edges[cur]) {
         maxa(inc_mx, fn(to, 1));
         sum += max(fn(to, 1), fn(to, 0));
      }
 
      if (with) {
         ret = inc_mx + 1;
      } else {
         ret = sum;
      }
 
      return ret;
   };
   cout << max(fn(0, 0), fn(0, 1));
 
}