아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

RGB트리

시간 제한1.5초메모리 제한1024 MB

요약
트리의 각 전구에 빨강, 초록, 파랑 중 한 색을 칠하되 인접한 전구는 다른 색이 되도록 하여 아름다움 합의 최댓값과 그 배정을 구한다.
난이도

보통10점 중 5점

유형
트리, 동적 계획법, DFS, 재귀
정답자
아직 제출이 없습니다

문제

RGB거리의 랜드마크인 RGB트리에는 전구가 NN개 있다. 전구의 번호는 11번부터 NN번까지이고, 각 전구는 빨강, 초록, 파랑 중 한 색의 빛을 낼 수 있다. 전구들은 트리 구조를 이루도록 연결되어 있으며, 인접한 전구끼리는 다른 색의 빛을 내야 한다. 각 전구가 내는 빛의 색에 따른 아름다움이 주어졌을 때, 아름다움의 합이 최대가 되도록 하는 방법을 구하시오.

입력

첫째 줄에 전구의 개수 NN이 주어진다. (1≤N≤500,000)(1\leq N\leq 500\\,000)

둘째 줄부터 NN째 줄에는 인접한 두 전구의 번호가 공백으로 구분되어 주어진다.

N+1N+1째 줄부터 2N2N째 줄에는 각 줄에 세 정수가 공백으로 구분되어 주어진다. N+iN+i째 줄에는 ii번 전구가 빨강, 초록, 파랑 빛을 낼 때의 아름다움 r_i,g_i,b_ir\_i,g\_i,b\_i가 주어진다. (1≤r_i,g_i,b_i≤1,000)(1 \leq r\_i,g\_i,b\_i \leq 1\\,000)

출력

첫째 줄에 모든 전구의 아름다움의 합의 최댓값을 출력한다.

둘째 줄에 아름다움이 최대가 될 때 전구의 색을 11번부터 순서대로 공백 없이 출력한다. 빨강일 경우 R, 초록일 경우 G, 파랑일 경우 B로 출력한다. 가능한 답이 여러 가지라면 아무거나 출력한다.

예제1

  1. 예제 1

    입력
    8
1 2
1 3
1 4
1 5
5 6
6 7
4 8
69 67 74
9 22 55
99 24 29
53 59 33
49 12 48
19 57 24
17 88 93
8 85 7
    예상 출력
    558
GBRRRGBG