← 返回题目列表

Codeforces · 1244/D

D. 画树

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的树。树是无向连接的无环图。

树的示例。

您必须将每个顶点绘制为三种颜色之一。对于每个顶点,您知道用每种颜色绘制它的成本。

您必须绘制顶点,以便由三个不同顶点组成的任何路径不包含任何颜色相同的顶点。换句话说,我们考虑所有三元组 $$$(x, y, z)$$$,使得 $$$x \neq y, y \neq z, x \neq z$$$,$$$x$$$ 通过边与 $$$y$$$ 连接,$$$y$$$ 通过边与 $$$z$$$ 连接。 $$$x$$$、$$$y$$$ 和 $$$z$$$ 的颜色应该成对不同。满足这个条件的画我们称之为好画。

你必须计算一幅好画的最低成本,并找到一幅最优的画。如果没有好画,请举报。

输入

第一行包含一个整数 $$$n$$$ $$$(3 \le n \le 100\,000)$$$ — 顶点数。

第二行包含整数序列 $$$c_{1, 1}, c_{1, 2}, \dots, c_{1, n}$$$ $$$(1 \le c_{1, i} \le 10^{9})$$$,其中 $$$c_{1, i}$$$ 是将第 $$$i$$$ 个顶点绘制到第一个顶点的成本颜色。

第三行包含整数序列 $$$c_{2, 1}, c_{2, 2}, \dots, c_{2, n}$$$ $$$(1 \le c_{2, i} \le 10^{9})$$$,其中 $$$c_{2, i}$$$ 是将第 $$$i$$$ 个顶点绘制到第二个顶点的成本颜色。

第四行包含整数序列 $$$c_{3, 1}, c_{3, 2}, \dots, c_{3, n}$$$ $$$(1 \le c_{3, i} \le 10^{9})$$$,其中 $$$c_{3, i}$$$ 是将第 $$$i$$$ 个顶点绘制到第三个顶点的成本颜色。

接下来是 $$$(n - 1)$$$ 行,每行包含两个整数 $$$u_j$$$ 和 $$$v_j$$$ $$$(1 \le u_j, v_j \le n, u_j \neq v_j)$$$ — 由第 $$$j$$$ 个无向边连接的顶点数。保证这些边代表一棵树。

输出

如果没有好画,就打印$$$-1$$$。

否则,在第一行打印一幅好画的最低成本。在第二行中打印 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le 3)$$$,其中第 $$$i$$$ 个整数应表示第 $$$i$$$ 个顶点的颜色。如果有多幅好画且成本最低,就打印其中任意一幅。

示例

输入 #1

3
3 2 3
4 3 2
3 1 3
1 2
2 3

输出 #1

6
1 3 2

输入 #2

5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 3

输出 #2

-1

输入 #3

5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 4

输出 #3

9
1 3 2 1 3

注意

在第一个示例中,所有顶点都应涂成不同的颜色。最佳方法是将第一个顶点绘制为颜色 $$$1$$$,将第二个顶点绘制为颜色 $$$3$$$,将第三个顶点绘制为颜色 $$$2$$$。这幅画的成本为 $$$3 + 2 + 1 = 6$$$。