Page 29 -

다음과 같습니다.

dp1[v] = max(dp1[c], dp2[c])
c:v의 자식 꼭짓점

dp2에 대해

v의 각 자식 꼭짓점 c를 루트로 하는 각 부분 트리에 대해 c를 고르지 않는 범위에서 c를 루트로
하는 각 부분 트리에 대한 최대 가중치의 총합을 구하면 되므로 다음과 같습니다.

dp2[v] = w(v) + dp1[c]
c:v의 자식 꼭짓점

이상을 정리하면 코드 18-1처럼 구현할 수 있습니다. 복잡도는 O(| V|)입니다.

코드 18-1 가중 최대 안정 집합 문제를 푸는, 트리의 동적 계획법
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using Graph = vector<vector<int>>;

// 입력
int N; // 꼭짓점 개수
vector<long long> w; // 각 꼭짓점의 가중치 18
Graph G; // 그래프

// 트리의 동적 계획법 테이블 어려운 문제 대책
vector<int> dp1, dp2;

void dfs(int v, int p = -1) {
// 먼저 각 자식 꼭짓점을 탐색함
for (auto ch : G[v]) {
if (ch == p) continue;
dfs(ch, v);
}

// 후위 순회 시에 동적 계획법
dp1[v] = 0, dp2[v] = w[v]; // 초기 조건
for (auto ch : G[v]) {
if (ch == p) continue;

385