백준 27501 - RGB트리 (C++)

문제 문제 링크 BOJ 27501 - RGB트리 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 인접한 정점 간 색이 겹치지 않도록 $3$가지 색을 이용해 칠할 때, 구할 수 있는 합의 최댓값과 그 과정을 구해보자.

제한 TL : $1.5$ sec, ML : $1024$ MB $1 ≤ N ≤ 500,000$ $1 ≤ r_i, g_i, b_i ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 문제 유형 자체는 아주 친숙한 유형이다. 단지 트리 위에서 진행할 뿐이다.

임의의 정점이 가질 수 있는 상태는 결국 $3$가지 중 하나가 될테니, 다음과 같이 점화식을 정의해보자. $dp[p][q] : $ $p$번 정점을 루트로 하는.....