[BOJ] 2213번: 트리의 독립집합

https://www.acmicpc.net/problem/2213

D1[x] : x를 root로 하는 subtree에서 x를 포함한 최대독립집합의 크기

D2[x] : x를 root로 하는 subtree에서 x를 포함하지 않는 최대독립집합의 크기으로 두면 자식들에 대해서

D1[cur] += D2[next],

D2[cur] += max(D1[next],D2[next])를 계산함으로서 DP 테이블을 채워나갈 수 있습니다.

집합을 복구해내기 위해서는 D2[cur]를 계산할 때 D1[next]가 더해졌는지 D2[next]가 더해졌는지를 저장해야 합니다.

https://github.com/blisstoner/BOJ/blob/master/2213.cpp