트리 DP

어떤 문제를 푸는가

트리 구조 위에서 정의된 최적화/카운팅 문제를, 각 서브트리의 답을 자식에서
부모로 모아 올리며 계산하는 기법입니다. 트리는 사이클이 없어 부모-자식
관계가 명확하므로, "이 정점을 루트로 하는 서브트리의 답"이 자연스러운 상태가
됩니다.

대표 예: 트리의 최대 독립 집합, 서브트리 크기/합, 트리 지름, 각 정점을 루트로
한 경우의 선택 비용 등.

상태 설계의 출발점

루트를 하나 정하면 모든 정점이 부모와 자식을 갖습니다. 보통 상태는

$$ dp[v][\dots] = v \text{를 루트로 하는 서브트리에서의 (조건별) 최적값} $$

으로 둡니다. "\(v\)를 선택했는가" 같은 조건이 추가 차원으로 붙습니다.

예시 — 트리의 최대 독립 집합

인접한 두 정점을 동시에 고를 수 없을 때, 가장 큰(또는 가중치 합이 큰) 정점
집합을 찾습니다. 정점 \(v\)에 대해 두 상태를 둡니다.

• dp[v][0] — \(v\)를 안 고를 때 서브트리의 최댓값.
• dp[v][1] — \(v\)를 고를 때 서브트리의 최댓값.

자식 \(c\)들에 대해:

$$ dp[v][0] = \sum_{c} \max(dp[c][0],\ dp[c][1]) $$
$$ dp[v][1] = w_v + \sum_{c} dp[c][0] $$

\(v\)를 고르면 자식은 못 고르고(\(dp[c][0]\)), \(v\)를 안 고르면 자식은 자유
(\(\max\))입니다. 답은 루트에서 \(\max(dp[root][0], dp[root][1])\).

왜 옳은가

서로 다른 서브트리는 부모를 통해서만 연결되므로, 한 자식의 선택은 다른 자식의
선택에 직접 영향을 주지 않습니다. 부모의 상태(고름/안 고름)만 고정하면 각
자식 서브트리는 독립적으로 최적화됩니다. 이 독립성이 "자식의 답을 합쳐
부모의 답을 만든다"는 트리 DP의 정당성을 줍니다.

복잡도

각 정점과 간선을 상수 번 처리하므로

$$ O(V) $$

(상태 차원이 작은 상수일 때). 상태가 추가 차원 \(K\)를 가지면 \(O(V \cdot K)\)
또는 자식 결합에 \(O(V \cdot K^2)\)가 되기도 합니다.

구현 형태

후위 순회(post-order)로 자식을 먼저 계산 한 뒤 부모를 계산합니다. DFS
재귀가 가장 자연스럽고, 정점이 많으면 스택 오버플로를 피해 명시적 스택이나
BFS 역순(위상 순서)으로 처리합니다. 다음 강의에서 구현과 리루팅(rerooting)을
봅니다.

최대 독립 집합 구현 (C++)

후위 순회로 자식을 먼저 채웁니다.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> adj;
vector<int> w;
vector<array<long long, 2>> dp;        // dp[v][0/1]

void dfs(int v, int par) {
    dp[v][0] = 0;
    dp[v][1] = w[v];
    for (int c : adj[v]) {
        if (c == par) continue;
        dfs(c, v);                     // 자식 먼저
        dp[v][0] += max(dp[c][0], dp[c][1]);
        dp[v][1] += dp[c][0];          // v를 고르면 자식은 못 고름
    }
}

int main() {
    cin >> n;
    adj.assign(n + 1, {}); w.assign(n + 1, 0); dp.assign(n + 1, {});
    for (int v = 1; v <= n; v++) cin >> w[v];
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]) << '\n';
}

큰 트리에서 스택 오버플로 피하기

\(N\)이 수십만이면 재귀 깊이가 위험합니다. 위상(부모 먼저 방문) 순서를
BFS로 만들고 역순으로 DP를 채우면 재귀 없이 같은 결과를 얻습니다.

// BFS로 방문 순서 order와 par 채운 뒤
for (int i = (int)order.size() - 1; i >= 0; i--) {
    int v = order[i];
    // v의 자식들은 order에서 v보다 뒤 → 이미 처리됨
}

리루팅 (Rerooting) — 모든 정점을 루트로 한 답

"각 정점을 루트로 했을 때의 답"을 정점마다 \(O(V)\)로 다시 구하면 \(O(V^2)\)라
느립니다. 리루팅 은 한 번의 DFS로 서브트리 답을 모은 뒤, 두 번째 DFS에서
부모 쪽 정보를 자식으로 내려보내 전체 \(O(V)\) 에 모든 루트의 답을 구합니다.

핵심 아이디어:

• 1차 DFS(down): 각 정점에 대해 "그 정점 아래 서브트리"의 값을 계산.
• 2차 DFS(up): 부모로부터 "그 정점 위쪽(나머지 트리)"의 값을 받아 합쳐
  "그 정점을 루트로 한 전체 답"을 완성. 자식으로 내려갈 땐 그 자식의 기여를
  뺀 값을 넘긴다.

예: 모든 정점에서의 "거리 합"이나 트리 지름 관련 양을 한 번에 구할 때 씁니다.

흔한 함정

• 부모로 되돌아가기 — if (c == par) continue;를 빼면 무한 루프/오답.
• 재귀 깊이 — 큰 트리는 명시적 스택이나 위상 순서로. 파이썬은
  sys.setrecursionlimit 상향 + 가능하면 반복 구현.
• 초기화 위치 — dp[v][1] = w[v]처럼 자기 기여를 먼저 넣고 자식을 합쳐야
  합니다.
• 합산 자료형 — 서브트리 합은 쉽게 커지므로 long long.

응용 패턴

• 트리 지름 — 각 정점에서 아래로 가장 긴 두 경로의 합의 최댓값.
• 서브트리 크기/합 — 카운팅·정렬·오일러 투어의 기반.
• 자식 결합이 무거운 DP — "그룹 짓기" 같은 문제는 자식을 배낭처럼 합침.
• 모든 루트 답 — 리루팅.

"자식 → 부모"라는 한 방향 의존을 잡으면, 트리 위의 거의 모든 최적화 문제가
한 번의 순회로 정리됩니다.

출제 신호

• 입력이 트리(\(N\)개 정점, \(N-1\)개 간선, 연결)이고 "정점/간선을 골라서
  무언가를 최대화·최소화"하는 문제 — 독립 집합(파티 초대), 정점 커버(감시 카메라),
  매칭, 색칠 경우의 수
• "각 서브트리에 대한 답", "트리의 지름", "어떤 정점을 루트로 했을 때의 답"
  (모든 루트 버전이면 리루팅까지)
• 제약 신호: \(N \le 10^5{\sim}10^6\) — 트리라서 간선이 적고, DFS 한 번
  \(O(N \times \text{상태 수})\)로 풀리는 크기입니다.

핵심 판별 질문: "부모의 답이 자식 서브트리들의 답만으로 조립되는가?"
그렇다면 트리 DP입니다.

풀이 결정 절차

1. 루트를 아무거나(보통 1번) 고정하고 트리를 "아래로" 봅니다.
2. 상태를 정의합니다 — dp[v][s] = "\(v\)의 서브트리에서, \(v\) 자신의 상태가
   \(s\)일 때의 최적값". \(s\)는 보통 "선택/비선택", "색", "커버됨/안 됨" 등 2~3가지.
3. 병합 규칙을 적습니다 — 자식들의 어떤 상태 조합이 부모의 각 상태와
   양립하는지 표로 그려 봅니다 (예: 독립 집합 — 부모 선택 시 자식은 비선택만).
4. 복잡도 검산 — 상태 \(k\)개면 \(O(Nk^2)\) (자식 병합 시 상태쌍)이 한계 안인지.
5. "모든 정점을 루트로" 묻는다면 1차 DFS(아래 방향) + 2차 DFS(부모 쪽 기여
   전달)의 리루팅을 계획합니다.

자주 하는 실수

• 파이썬 재귀 한도 — \(N \ge 10^4\)면 기본 한도(1000)를 넘습니다.
  sys.setrecursionlimit(300000)로도 깊은 일자 트리에선 세그폴트가 날 수
  있어, 명시적 스택의 반복 DFS가 가장 안전합니다.

# 후위 순서를 만들어 두면 DP는 그냥 역순 for 문이 됩니다
order, parent = [], [0] * (n + 1)
stack = [1]
visited = [False] * (n + 1)
visited[1] = True
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            parent[v] = u
            stack.append(v)
for u in reversed(order):              # 자식이 항상 먼저 처리됨
    for v in adj[u]:
        if v != parent[u]:
            dp[u][0] += max(dp[v][0], dp[v][1])
            dp[u][1] += dp[v][0]

• 부모로 되돌아가는 간선 — 무방향 인접 리스트에서 v != parent[u] 검사를
  빼먹으면 무한 재귀(또는 이중 계산)가 됩니다. visited 배열 방식도 좋습니다.
• 상태 정의에 "자신의 상태"를 안 넣음 — dp[v] 하나로 뭉뚱그리면 부모와의
  양립 조건을 표현할 수 없어 병합이 불가능해집니다. 막히면 상태를 쪼개세요.
• 지름을 한 번의 DFS 값으로 착각 — 정점 \(v\)를 지나는 최장 경로는 "자식 쪽
  최장 팔 상위 2개의 합"입니다. 1등 팔만 들고 가면 틀립니다.
• 리루팅에서 자기 자신 기여 제거 누락 — 부모가 자식에게 답을 물려줄 때,
  부모 답에서 그 자식의 기여를 뺀 값을 전달해야 합니다.

연습 방법

사이드바 연습 목록의 독립 집합형(파티 초대) 문제로 2-상태 DP를 익히고,
트리 지름 → 정점 커버(감시) → 리루팅 문제로 확장하세요. 새 문제마다
"상태 정의 / 병합 표 / 복잡도" 세 줄을 코드 전에 쓰는 습관이 트리 DP
실력의 본체입니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어
레이팅 CLASS 보너스에 반영됩니다.