CF1244D Paint the Tree

给定一棵包含 $n$ 个顶点的树。树是一个无向、连通且无环的图。  树的示例。 你需要将每个顶点涂成三种颜色中的一种。对于每个顶点，已知将其涂成每种颜色的花费。 你需要对顶点进行染色，使得任意由恰好三个不同顶点组成的路径中，所有顶点的颜色都不相同。换句话说，考虑所有三元组 $(x, y, z)$，满足 $x \neq y, y \neq z, x \neq z$，且 $x$ 与 $y$ 有边相连，$y$ 与 $z$ 有边相连。$x$、$y$、$z$ 的颜色应两两不同。我们称满足此条件的染色为“好染色”。 你需要计算好染色的最小花费，并给出一种最优染色方案。如果不存在好染色，请输出相应信息。

第一行包含一个整数 $n$ $(3 \leq n \leq 100\,000)$，表示顶点数。 第二行包含 $n$ 个整数 $c_{1,1}, c_{1,2}, \dots, c_{1,n}$ $(1 \leq c_{1,i} \leq 10^9)$，其中 $c_{1,i}$ 表示将第 $i$ 个顶点染成第一种颜色的花费。 第三行包含 $n$ 个整数 $c_{2,1}, c_{2,2}, \dots, c_{2,n}$ $(1 \leq c_{2,i} \leq 10^9)$，其中 $c_{2,i}$ 表示将第 $i$ 个顶点染成第二种颜色的花费。 第四行包含 $n$ 个整数 $c_{3,1}, c_{3,2}, \dots, c_{3,n}$ $(1 \leq c_{3,i} \leq 10^9)$，其中 $c_{3,i}$ 表示将第 $i$ 个顶点染成第三种颜色的花费。 接下来 $n-1$ 行，每行包含两个整数 $u_j$ 和 $v_j$ $(1 \leq u_j, v_j \leq n, u_j \neq v_j)$，表示第 $j$ 条无向边连接的两个顶点编号。保证这些边构成一棵树。

如果不存在好染色，输出 $-1$。 否则，第一行输出好染色的最小花费。第二行输出 $n$ 个整数 $b_1, b_2, \dots, b_n$ $(1 \leq b_i \leq 3)$，其中 $b_i$ 表示第 $i$ 个顶点的颜色编号。如果有多种最优方案，输出任意一种。

在第一个样例中，所有顶点都应染成不同的颜色。最优方案是将第一个顶点染成颜色 $1$，第二个顶点染成颜色 $3$，第三个顶点染成颜色 $2$。染色的总花费为 $3 + 2 + 1 = 6$。 由 ChatGPT 4.1 翻译