巴哈明从过去来拜访阿里——他来自未来。他还带来了一棵古树作为礼物送给阿里。他注意到它的一些顶点失去了颜色。巴哈明需要重新绘制这些顶点,但他正忙于修复他的时间机器。幸运的是(或不幸的是),恐龙现在可以处理此类任务——当然是收费的。他需要你的帮助以最小的成本找到颜色。所以他给你的问题如下。
给定一个有根树$$$^{\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$$$。
如果有多种着色且具有最小可能 成本 树的,您可以输出其中任何一个。
示例
输入复制
44 45 5 5 51 0 2 31 21 31 45 23 1 4 1 51 2 1 2 21 42 13 44 511 33 1 4 3 1 4 3 1 4 5 60 0 0 2 1 2 1 2 2 1 11 22 32 42 52 61 77 87 910 33 114 32 3 2 32 1 0 03 11 22 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$$$。
- $$$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$$$。
可以证明没有着色 存在小于 $$$7$$$ 的 成本 树的 。