트리 DP (Tree Dynamic Programming)

정의

트리 DP (Tree Dynamic Programming) 는 트리 구조에서 각 서브트리의 최적해를 post-order DFS 로 계산하여 전체 트리의 답을 구하는 정형. dp[v] = f(dp[child1], dp[child2], ...) 형태의 재귀 점화식.

대표 패턴: 트리 독립집합, 트리 지름, 트리 knapsack, LCA preprocessing.

문제 상황과 동기

트리에서 “각 정점을 선택/비선택” / “경로 최대/최소” / “서브트리 합” 같은 문제는 일반 그래프는 NP-hard 지만, 트리는 사이클 없음 + 경로 유일성 으로 O(N) DP 가능.

• naive: 모든 부분집합 2^N 조사 → N=10^5 불가능.
• 트리 DP: DFS 한 번에 각 서브트리의 최적값 모아서 O(N).

핵심 통찰: 서브트리의 답은 자식들의 답으로부터 독립적으로 계산 가능. (트리 = DAG 의 특수 케이스)

PS 에서 “트리 + 최적화” 문제는 거의 트리 DP.

시각화

핵심 아이디어

post-order DFS

1. 리프부터 dp 값 계산 (base case)
2. 자식들의 dp 값으로 현재 정점의 dp 계산 (재귀)
3. 루트까지 도달하면 전체 답

상태 정의

보통 dp[v][state] 형태:

• state = 0: v 를 선택 안 함
• state = 1: v 를 선택함

또는 dp[v] = (선택, 비선택) 튜플.

점화식

예: 트리 독립집합 (maximum independent set)

• dp[v][0] = v 를 선택 안 함 → 자식은 선택/비선택 모두 가능 → max(dp[child][0], dp[child][1])
• dp[v][1] = v 를 선택함 → 자식은 반드시 비선택 → dp[child][0]

dp[v][0] = Σ max(dp[child][0], dp[child][1])  for child in children(v)
dp[v][1] = weight[v] + Σ dp[child][0]         for child in children(v)

알고리즘

Input: 루트 트리, 각 정점 가중치 w[v]
Output: 독립집합 최대 가중치 합

dfs(v):
    dp[v][0] = 0
    dp[v][1] = w[v]
    for each child u of v:
        dfs(u)
        dp[v][0] += max(dp[u][0], dp[u][1])
        dp[v][1] += dp[u][0]

main:
    dfs(root)
    return max(dp[root][0], dp[root][1])

구현

// 트리 독립집합 (maximum independent set)
// dp[v][0] = v 비선택, dp[v][1] = v 선택
#include <bits/stdc++.h>
using namespace std;
​
int n;
vector<int> adj[100005];
int w[100005];
long long dp[100005][2];
​
void dfs(int u, int p) {
  dp[u][0] = 0;
  dp[u][1] = w[u];
  for (int v : adj[u]) {
      if (v == p) continue;
      dfs(v, u);
      dp[u][0] += max(dp[v][0], dp[v][1]);
      dp[u][1] += dp[v][0];
  }
}
​
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> w[i];
  for (int i = 0; i < n - 1; i++) {
      int u, v; cin >> u >> v;
      u--; v--;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  int root = 0;
  dfs(root, -1);
  cout << max(dp[root][0], dp[root][1]) << "\n";
}

# 트리 독립집합 with sys.setrecursionlimit
import sys
sys.setrecursionlimit(200_000)
input = sys.stdin.readline
​
n = int(input())
w = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n - 1):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  adj[u].append(v)
  adj[v].append(u)
​
dp = [[0, 0] for _ in range(n)]
​
def dfs(u, p):
  dp[u][0] = 0
  dp[u][1] = w[u]
  for v in adj[u]:
      if v == p: continue
      dfs(v, u)
      dp[u][0] += max(dp[v][0], dp[v][1])
      dp[u][1] += dp[v][0]
​
dfs(0, -1)
print(max(dp[0][0], dp[0][1]))

// 트리 독립집합 with ArrayList
import java.util.*;
import java.io.*;
​
public class Main {
  static int n;
  static ArrayList<Integer>[] adj;
  static int[] w;
  static long[][] dp;
  
  static void dfs(int u, int p) {
      dp[u][0] = 0;
      dp[u][1] = w[u];
      for (int v : adj[u]) {
          if (v == p) continue;
          dfs(v, u);
          dp[u][0] += Math.max(dp[v][0], dp[v][1]);
          dp[u][1] += dp[v][0];
      }
  }
  
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      n = Integer.parseInt(br.readLine());
      w = new int[n];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) w[i] = Integer.parseInt(st.nextToken());
      
      adj = new ArrayList[n];
      for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
      dp = new long[n][2];
      
      for (int i = 0; i < n - 1; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken()) - 1;
          int v = Integer.parseInt(st.nextToken()) - 1;
          adj[u].add(v);
          adj[v].add(u);
      }
      dfs(0, -1);
      System.out.println(Math.max(dp[0][0], dp[0][1]));
  }
}

5
10 20 30 40 50
1 2
1 3
2 4
2 5

110

복잡도

트리 DP 는 항상 O(N) 시간, O(N) 공간.

대표 문제 패턴

1. 트리 독립집합

위 구현 참고. 인접한 정점을 동시 선택 불가 → dp[v][0/1].

2. 트리 지름

두 리프 사이 최대 거리. 두 가지 방법:

• DFS 2회: 임의 정점 → 가장 먼 정점 u → u 에서 가장 먼 정점 v (O(N))
• 트리 DP: dp[v] = “v 를 끝점으로 하는 최장 경로” (O(N))

3. 트리 knapsack

각 서브트리에서 k 개 선택, 가중치 최대화. dp[v][k] = 서브트리 v 에서 k 개 선택 최대값. 자식들의 dp 를 합쳐서 knapsack DP → O(N^2) (k 상태).

4. LCA preprocessing

binary lifting 으로 2^k 번째 조상 전처리. sparse table DP.

변형 / 활용

re-rooting

루트를 바꿔가며 각 정점을 루트로 했을 때의 답 계산. DFS 2회로 O(N).

1. 첫 DFS: 루트 → 리프 방향 dp
2. 둘째 DFS: 부모 → 자식 방향으로 부모의 dp 값 전달

small-to-large / HLD

서브트리 병합이 O(N log N) 인 경우. 작은 서브트리를 큰 쪽에 합침.

centroid decomposition

트리 분할 정복. 중심을 제거하며 O(N log N) 에 문제 해결.

함정

1. post-order 순서

자식의 dp 를 먼저 계산하지 않고 부모 계산하면 잘못된 답. DFS 재귀 순서 주의.

2. 루트 위치

문제에서 루트를 명시 안 하면 임의 정점 (보통 0 또는 1) 을 루트로. 트리는 루트 위치 상관없이 같은 답이 나와야 하는지 확인.

3. 상태 정의

독립집합은 2 상태, knapsack 은 k+1 상태. 상태 수가 많으면 공간 / 시간 복잡도 증가.

4. 재귀 깊이

Python 은 sys.setrecursionlimit() 필수. C++ / Java 도 N=10^6 일자 트리는 스택 오버플로우 가능 → BFS 로 위상 정렬 후 반복문.

BOJ 연습 문제

참고

• 트리
• 깊이 우선 탐색
• 동적 계획법
• 최소 공통 조상