백준 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$번 정점을 루트로하는 서브 트리에서, $p$번 정점을 색 $q$로 칠했을 때 얻을 수 있는 최대 합.

그럼 각각의 색$(r : 0, g : 1, b : 2)$에 대해 서브 트리 간 상태 전이는

• $dp[p][0] = $$c[p][0] + max(dp[i][1], dp[i][2])$
• $dp[p][1] = $$c[p][1] + max(dp[i][0], dp[i][2])$
• $dp[p][2] = $$c[p][2] + max(dp[i][0], dp[i][1])$

로 쉽게 추릴 수 있다.

---

이제 역추적이 관건인데, 이 문제 를 풀어 보았다면 어렵지 않게 할 수 있겠지만 아니더라도 괜찮다.

트리에서 역추적은 보통 비선형 구조임에 따라 $dfs$로 따라간다.
이때 그냥 따라가는 것이 아닌 이전 작업에서 기록된 $dp$값들을 기준으로 따라가야 한다.

$max(dp[1][x])$인 $x$를 시작으로 위 상태 전이 식을 그대로 따라가면 된다.

전체 코드

#include<bits/stdc++.h>
#define N 500001
using namespace std;
using ll = long long;
 
vector <int> Gr[N];
int n, c[N][3];
ll dp[N][3];
char r[N];
 
ll f(int p, int q, int o)
{
    ll& t(dp[p][q]);
    if (!~t)
    {
        t = c[p][q];
        for (int& i : Gr[p])
            if (i ^ o)
            {
                if (!q) t += max(f(i, 1, p), f(i, 2, p));
                else if (q & 1) t += max(f(i, 0, p), f(i, 2, p));
                else t += max(f(i, 0, p), f(i, 1, p));
            }
    }
    return t;
}
void g(int p, int q, int o)
{
    r[p] = q ? (q > 1 ? 'B' : 'G') : 'R';
    for (int& i : Gr[p])
        if (i ^ o)
        {
            if (!q) g(i, dp[i][1] > dp[i][2] ? 1 : 2, p);
            else if (q & 1) g(i, dp[i][0] > dp[i][2] ? 0 : 2, p);
            else g(i, dp[i][1] > dp[i][0], p);
        }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    memset(dp, -1, sizeof dp); cin >> n;
 
    for (int i, j, o{}; ++o < n;) cin >> i >> j, Gr[i].push_back(j), Gr[j].push_back(i);
    for (int i(1); i <= n; i++) cin >> c[i][0] >> c[i][1] >> c[i][2];
 
    cout << max({ f(1, 0, 1), f(1, 1, 1), f(1, 2, 1) }) << '\n';
 
    g(1, dp[1][dp[1][1] > dp[1][0]] > dp[1][2] ? dp[1][1] > dp[1][0] : 2, 1);
    for (int i(1); i <= n; cout << r[i++]);
}

comment

끝