백준 2213 - 트리의 독립집합 (C++)

문제 문제 링크 BOJ 2213 - 트리의 독립집합 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리의 '최대 독립집합'의 크기와 이를 구성하는 정점들을 구해보자.

제한 TL : $2$ sec, ML : $128$ MB $1 ≤ N, C_i ≤ 10,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 트리$dp$ 역추적의 바이블같은 문제이다. 임의의 정점이 가질 수 있는 상태는 결국 둘 중 하나다.

최대 독립집합에 포함 되었을 때( $1$ ) ? 아니었을 때( $0$ ) ?

이에 따라 다음과 같이 점화식을 정의해보자. $dp[i][j] :$ $i$번 정점을 루트로 하는 서브 트리에서, $i$번 정점의 포함 상태가 $j$일.....