E. Hanging Hearts

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

어떤 노드 uu와 그것의 부모 pp가 있다고 하자.

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

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

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

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

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

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

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

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

반대로 pp를 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));
 
}

Comments

You may also enjoy