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

Problem - E - Codeforces

보자마자 트리디피 인 것은 알았지만 한 가지 착각한 것 때문에 시간이 너무 오래 걸렸다.

dp[i] : i를 루트로 하는 서브트리 내에서 정답

이라고 했을 때 dp[i] 는 max(모든 자식 dp[j] 를 더한 값, max(dp[j]) + 1)이라고 생각했다.

여기서 간과한 사실은 이렇게 구현하면 max(dp[j]) + 1)에 포함된 노드들 중에 모든 자식 dp[k]를 더한 값이 존재할 수 있다는 것이다. max(dp[j]) + 1로 구한 값은 항상 그 자식들도 max(dp[k]) + 1로 구해져야 한다. 생각해 보면 max(dp[j]) + 1이라는 값은 트리의 깊이이다. 따라서 트리의 깊이와 모든 자식 dp[j] 를 더한 값은 분리해야 한다.

그렇다면 dp[i] = max(모든 자식 dp[j] 를 더한 값, 트리의 깊이)로 설정해야 한다.