← 返回题目列表

Codeforces · 2127/E

E. 古树

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

巴哈明从过去来拜访阿里——他来自未来。他还带来了一棵古树作为礼物送给阿里。他注意到它的一些顶点失去了颜色。巴哈明需要重新绘制这些顶点,但他正忙于修复他的时间机器。幸运的是(或不幸的是),恐龙现在可以处理此类任务——当然是收费的。他需要你的帮助以最小的成本找到颜色。所以他给你的问题如下。

给定一个有根树$$$^{\text{*}}$$$,共有 $$$n$$$ 个顶点,其中顶点 $$$1$$$ 是根。每个顶点都有一个整数权重 $$$w_i$$$ 和一个颜色 $$$c_i$$$,其中颜色是 $$$1$$$ 和 $$$k$$$ 之间的整数。然而,一些顶点失去了颜色,用 $$$c_i = 0$$$ 表示。

我们称顶点为$$$v$$$ 可爱 如果有 存在 两个顶点 $$$x$$$ 和 $$$y$$$,使得

  • $$$\operatorname{lca}(x, y)$$$$$$^{\text{†}}$$$ $$$= v$$$,
  • $$$c_x = c_y$$$,并且
  • $$$c_x \neq c_v$$$。

的 成本 树的 是所有树的权重之和 可爱 顶点。

您必须将 $$$1$$$ 和 $$$k$$$ 之间的颜色分配给所有失去颜色的顶点。找出可能的最小值 成本 树的 在所有有效着色中并提供尽可能最小的着色 成本 树的.

$$$^{\text{*}}$$$树是没有环的连通图。 有根树是一棵树,其中一个顶点是特殊的,称为根。

$$$^{\text{†}}$$$$$$\operatorname{lca}(x, y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最低共同祖先 (LCA)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$, $$$2 \leq k \leq n$$$) — 顶点数和颜色数。

第二行包含 $$$n$$$ 整数 $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \leq w_i \leq 10^9$$$) — 顶点的权重。

第三行包含 $$$n$$$ 整数 $$$c_1,c_2,\ldots,c_n$$$ ($$$0 \leq c_i \leq k$$$) — 顶点的颜色。 $$$c_i=0$$$ 表示顶点 $$$i$$$ 失去了颜色。

然后是 $$$n−1$$$ 行,第 $$$i$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$) — 第 $$$i$$$ 条边连接的两个顶点。

保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在第一行输出一个整数 - 可能的最小值 成本 树的 在所有有效着色中。

在第二行输出 $$$n$$$ 整数 $$$c'_1, c'_2, \ldots, c'_n$$$ — 最小可能的着色 成本 树的。您需要保证:

  • $$$c'_i = c_i$$$ 如果 $$$c_i \neq 0$$$;
  • $$$1 \leq c'_i \leq k$$$ 如果 $$$c_i = 0$$$。

如果有多种着色且具有最小可能 成本 树的,您可以输出其中任何一个。

示例

输入
复制

4
4 4
5 5 5 5
1 0 2 3
1 2
1 3
1 4
5 2
3 1 4 1 5
1 2 1 2 2
1 4
2 1
3 4
4 5
11 3
3 1 4 3 1 4 3 1 4 5 6
0 0 0 2 1 2 1 2 2 1 1
1 2
2 3
2 4
2 5
2 6
1 7
7 8
7 9
10 3
3 11
4 3
2 3 2 3
2 1 0 0
3 1
1 2
2 4

输出
复制

0
1 4 2 3
3
1 2 1 2 2
7
2 3 1 2 1 2 1 2 2 1 1
0
2 1 3 1

注意

在第一个测试用例中,缺失的颜色有四种选择:

  • $$$c_2 = 1$$$ 没有顶点 可爱,所以 成本 树的 是 $$$0$$$;
  • $$$c_2 = 2$$$ 使顶点 $$$1$$$ 可爱,因为 $$$c_2 = c_3 = 2$$$,$$$\operatorname{lca}(2, 3) = 1$$$ 和 $$$c_1 \neq 2$$$。因此, 成本 树的 是 $$$w_1 = 5$$$;
  • $$$c_2 = 3$$$ 使顶点 $$$1$$$ 可爱,因为 $$$c_2 = c_4 = 3$$$,$$$\operatorname{lca}(2, 4) = 1$$$ 和 $$$c_1 \neq 3$$$。因此, 成本 树的 是 $$$w_1 = 5$$$;
  • $$$c_2 = 4$$$ 没有顶点 可爱,所以 成本 树的 是 $$$0$$$。

因此,最小可能 不同颜色之间的 成本 树的 是$$$0$$$。

在第二个测试用例中,每个顶点都有一种颜色。所以目前 成本 树的 不可更改。由于我们有 $$$c_5 = c_2 = 2$$$、$$$\operatorname{lca}(2, 5) = 1$$$ 和 $$$c_1 \neq 2$$$,所以顶点 $$$1$$$ 是 可爱 和当前 成本 树的 等于 $$$w_1 = 3$$$。

在第三个测试用例中,成本最小的可能着色如下所示:

其他一些有效的颜色是:

  • $$$c = [3, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1]$$$ 使得顶点 $$$1, 2, 3, 7$$$ 可爱:
    • $$$\操作员名称{lca}(4, 8) = 1$$$;
    • $$$\操作员名称{lca}(3, 4) = 2$$$;
    • $$$\操作员名称{lca}(10, 11) = 3$$$;
    • $$$\操作员名称{lca}(8, 9) = 7$$$。
    提到的所有顶点对都具有与其 LCA 不同的颜色。所以 成本 树的 将是 $$$w_1 + w_2 + w_3 + w_7 = 11$$$。
  • $$$c = [3, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1]$$$ 使得顶点 $$$1, 2, 7$$$ 可爱:
    • $$$\操作员名称{lca}(5, 7) = 1$$$;
    • $$$\操作员名称{lca}(5, 11) = 2$$$;
    • $$$\操作员名称{lca}(8, 9) = 7$$$。
    提到的所有顶点对都具有与其 LCA 不同的颜色。所以 成本 树的 将是 $$$w_1 + w_2 + w_7 = 7$$$。

可以证明没有着色 存在小于 $$$7$$$ 的 成本 树的 。