Graph DP: 트리/DAG 위 DP

Graph DP, 트리 DP, Tree DP, DAG DP

정의

Graph DP 는 그래프 구조를 이용한 DP. 사이클 없는 그래프 (트리, DAG) 에서 특히 자연스러움.

Tree DP

루트 트리에서 자식 서브트리 결과를 조합.

void dfs(int u, int p) {
    dp[u] = 1;   // 자기 자신
    for (int v : adj[u]) if (v != p) {
        dfs(v, u);
        dp[u] += dp[v];   // 서브트리 크기 예
    }
}

Rerooting (모든 루트 답)

Tree DP 는 특정 루트 기준. 모든 정점을 루트로 했을 때의 답이 필요하면 rerooting.

두 번의 DFS:

1. 임의 루트 r 로 down DP: dp_down[u] = u 서브트리 정보
2. Down 정보 이용 up DP: dp[u] = u 를 루트로 한 전체 답

O(N).

DAG DP

DAG 는 위상 정렬 후 순서대로 계산.

• longest path: dp[v] = max(dp[u] + w) for u -> v
• path 수 세기: dp[v] = sum(dp[u]) for u -> v

참고

• Topological Sorting
• Tree Diameter
• DP Bitfield