27501번 - RGB트리 스페셜 저지

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

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

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

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

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

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