문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

Naive 하게 각 마을을 포함시키거나 빼면서 모든 경우를 조사하여 풀 수 있다. 그러나 시간 복잡도는 O(2^N)이다. 대신, xxoxA oxoxA 두 순서로 이루어진 경우가 존재할 때, 뒤에 A 순서는 중복되므로 다시 계산해 줄 필요가 없다. 따라서, Dynamic Programming으로 풀 수 있다.

Algorithm

1번 마을을 root 삼아, 다음과 같이 DFS 하게 dp를 채운다.

• 현재 마을의 모든 자손에 대해 loop
  1. DFS( child)
  2. dp[current].include += dp[child].exclude
  3. dp[current].exclude += max( dp[child].include, dp[child].exclude)

(이때, oxxxo 같은 경우는 자연스럽게 최종 값이 되지 못한다.)

Data Structure

• dp_data dp[N+1]: 각 마을의 dp 값 저장
• dp_data : 현재 마을을 포함한 값과 포함하지 않은 값의 최대를 저장
• inhabitants[]: 각 마을의 거주자 수 저장

결과

Other

시간 복잡도는 O(N) 이다.