80. Tree DP

트리에서의 동적 계획법(Tree DP)에 대해 다룬다. 트리에 대한 내용을 전혀 다루지 않은 상태에서 트리 DP를 다루는 건 순서가 뒤바뀐 느낌이지만 트리 DP가 트리와 DP 중 DP에 더 가깝기 때문에 여기서 다루었다. 트리에 대한 내용은 Chapter H에서 다루며, 기본적인 내용은 이 글을 참고하면 된다.

 

일반적으로 트리 DP를 시작하는 정점은 트리의 루트이며 루트 없는 트리가 주어지는 경우 임의의 정점을 하나 선택하면 되는 경우가 많다. 또한 자식 노드들의 DP 정보를 바탕으로 부모 노드의 DP 정보를 갱신하는 방법과 부모 노드의 DP 정보를 바탕으로 자식 노드의 DP 정보를 갱신하는 방법으로 구분할 수 있다. 일반적으로 전자가 더 많이 사용되는 것 같다.

 

[연습문제]

 

BOJ 15681. 트리와 쿼리 (Gold V)

리프 노드의 DP 값은 $1$, 나머지 노드의 DP 값은 $\sum($자식 노드들의 DP 값$) + 1$이다. 문제 아래쪽에 설명이 꽤 잘 되어 있는 편이니 읽어 보는 것도 좋다.

 

BOJ 2533. 사회망 서비스(SNS) (Gold III)

아무 노드나 하나를 골라서 루트 노드로 하고 DP 값을 구한다. 각각의 노드에 대해 '그 노드가 표현하는 사람이 얼리 아답터인 경우'와 그렇지 않은 경우 '그 노드를 루트로 하는 서브트리에 속한 얼리 아답터의 최대값'을 저장하는 방식으로 풀 수 있다.

 

BOJ 20171. Dessert Café (Gold II)

아파트 단지 중 아무거나 하나를 골라서 루트 노드로 하면 트리 DP로 쉽게 풀린다. 각각의 정점에 대해 그 정점을 루트로 하는 서브트리 중 아파트 단지의 수를 DP 값으로 하면 DP 값이 $1$ 이상인 정점의 개수가 답이 된다.

 

BOJ 2213. 트리의 독립집합 (Gold I)

2533번과 비슷한 방법으로 DP 값을 정한다. 이 문제는 실제로 독립집합을 구하는 과정이 있어서 2533번보다 약간 더 어려운데 각각의 정점이 독립집합에 포함되는 경우와 그렇지 않은 경우의 DP 값 중 어느 쪽이 더 큰지를 체크해 놓으면 각각의 정점을 독립집합에 포함시킬지의 여부를 정할 수 있다. DP 값을 루트 노드부터 정하는 방법으로도 풀 수 있는데 구현 시 약간 주의해야 한다.

 

CF 1336A. Linova and Kingdom (1600)

수도부터 차례대로 개발한다고 하면 어떤 도시를 개발했을 때 증가하는 행복도의 합은 $($그 도시를 루트로 하는 서브트리의 크기$)-($그 도시의 깊이$)$이다. 따라서 트리 DP로 각 도시의 깊이와 서브트리의 크기를 구한 다음 정렬해서 하나씩 선택하면 된다.

 

CF 1528A. Parsa's Humongous Tree (1600)

노드 $i$에 $l_i, r_i$ 중 한 값을 대응시키는 것이 최적의 전략이다. 따라서 노드 $i$에 값 $l_i$가 대응된 경우와 $r_i$가 대응된 경우의 beauty의 최대값을 트리 DP로 구하면 된다.

 

CF 1401D. Maximum Distributed Tree (1800)

모든 경로가 각각의 간선을 지나는 횟수는 그 간선을 제거했을 때 생기는 두 컴포넌트의 크기의 곱과 같다. 두 컴포넌트의 크기의 합은 항상 $n$이므로 트리 DP로 각각의 정점을 루트로 하는 서브트리의 크기를 구해 놓으면 어떤 간선을 더 많이 지나가는지 구할 수 있다. 값이 큰 소수를 더 많이 지나가는 간선에 대응하는 것이 이득이므로 $m$이 $(n-1)$보다 큰 경우와 그렇지 않은 경우로 나눠서 처리하면 된다.

 

CF 1153D. Serval and Rooted Tree (1900)

리프 노드의 DP 값은 $1$로 두고, 나머지 노드의 DP 값은 다음과 같이 정한다.

 

• $\min$ 노드의 DP 값은 자식 노드들의 DP 값의 최소값이다.
• $\max$ 노드의 DP 값은 자식 노드들의 DP 값의 합이다.

$($리프 노드의 수$)-($루트 노드의 DP 값$)+1$이 답이 된다.

 

CF 1187E. Tree Painting (2100)

각각의 정점을 루트로 하는 서브트리의 크기를 트리 DP로 구한 다음 각 간선에 대해 간선 양쪽에 존재하는 각각의 컴포넌트에 대해 그 컴포넌트에 존재하는 노드들의 DP 값의 합을 구해야 한다. 따라서 DP 값을 정점이 아닌 간선에 대해서 구하는 것이 편리하고, 간선의 한쪽 방향을 처리할 때 반대쪽 방향도 처리해 주어야 한다. 구해진 값을 바탕으로 얻을 수 있는 최대 점수를 계산한다.

 

CF 1156D. 0-1-Tree (2200)

$1-$간선과 $0-$간선을 따로 처리한다. 각각의 간선에 대해 그 간선과 같은 종류의 간선을 따라갔을 때 도달할 수 있는 정점의 개수를 트리 DP로 구하고, DP 값을 바탕으로 각각의 정점에서 $1-$간선만을 따라갔을 때 도달할 수 있는 정점의 수 $x$ 와 $0-$간선만을 따라갔을 때 도달할 수 있는 정점의 수 $y$를 계산한다. 이제 $xy-1$을 다 더하면 된다.

 

BOJ 27479. Dog Snacks (Platinum III)

CF 1453E. Dog Snacks (2300)

약간 어려운 트리 DP 문제이다. $d_i$를 노드 $i$의 깊이라고 하고 다음과 같이 $x_i, y_i, z_i$를 정의한다. $j$는 $i$의 자식 노드들을 의미하며 $y_i$와 $z_i$는 노드 $i$에 충분한 수의 자식 노드가 있을 때에만 정의된다. $\text{second } \max$는 두 번째로 큰 값을 의미한다.

• $x_i = \begin{cases} \min(x_j) & (i \ne Leaf) \\ d_i & (i = Leaf) \end{cases}$
• $y_i = \max(x_j)$
• $z_i = \text{second } \max(x_j)$

문제에서 구하는 답은 $\max(\max(y_i - d_i + 1), y_1, z_1+1)$ $(2 \le i \le n)$ 이다.

 

→ solved.ac tag: dp_tree