Codeforces Round #263(Div.1) B. Appleman and Tree(트리 DP)

제목: LINK
나무에 노드마다 흰색이나 검은색을 주어라.한 변의 집합을 삭제해서 남은 모든 나무 안에 있고 단지 하나의 노드만 검은색으로 만들 수 있다.이렇게 집합된 수량을 구하다.분명히 트리 DP입니다.dp[n][2], dp[i][j]는 i가 있는 이 점에 있는 하위 트리의 구분 상황이 모두 조건(부분마다 검은 점이 하나)만 있는 상황을 나타낸다. dp[i][0]는 i 노드를 포함하는 이 부분에 검은 점이 없는 집합 수량을 나타낸다. dp[i][1]은 이 부분에 검은 점이 있는 집합 수량을 나타낸다.각 노드에 대해 하위 트리(뿌리 노드 v)(연결의 가장자리를 x로 설정)를 계산할 때 dp[i][0]는 dp[i][0]*dp[v][1]+dp[i][0]*dp[v][0]로 처리하고 처리된 것은 반드시 dp[i][0]를 취하고 x를 취하면 하위 트리는 dp[v][0]를 취하며 x를 취하지 않으면 하위 트리는 dp[v]를 취한다[1].dp[i][1]은 dp[i][1]*(dp[v][0]+dp[v][1])+dp[i][0]*dp[v][1]이고 처리된 것은 dp[i][1], x는 dp[v][0], 안 받으면 dp[v][1]이다.만약에 처리된 dp[i][0]를 찾으면 x는 반드시 취하고 dp[v][1](ps: dp[v][0]를 곱해야 한다. 원하지 않으면 v점의 부분에 검은 점이 없는 상황이 나타난다)

#include
#include
#include
#include
#include
#include
#include
#include
#include