문제

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

Problem Analysis

Naive 하게 풀려면, 다음과 같이 DFS를 진행하면서, 각 node를 포함시킬 때와 포함시키지 않을 때를 모두 조사하여 가능한 최대를 구하면 된다. 그러나, 이 경우 시간 복잡도는 O(2^N)이다.

이때, 각 node에서의 최대는, 다음과 같이 여러 번 필요하다. 따라서, Dynamic Programming으로 개선할 수 있다.

Algorithm

편하게 node-1을 root로 보고 진행한다.

1. Dynamic Programming으로, 각 node의 두 가지 dp 값을 구한다.

   • 현재 node dp에 weight를 더한다.
   • 각 자손에 대해 iterative 하게 다음을 수행
     - 자손으로 DFS
     - 현재 node를 포함시킨다면, 자손 node의 dp.exclude를 더한다.
     - 현재 node를 포함시키지 않는다면, 자손 node dp.include 와 자손 node dp.exclude 중 최대를 선택하여 더한다.

2. dp를 역추적하여, 경로를 구한다.

Data Structure

• adjList[]: tree 저장
• dp_data dp[]: 각 node에 대한 dp_data를 저장
• dp_data: 포함한 값, 포함하지 않은 값 두 가지 value를 저장

결과

Other

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