CF2127E Ancient Tree

Bahamin 从过去来到未来拜访 Ali，并带来了一棵古老的树作为礼物。他发现树上的一些顶点失去了颜色。Bahamin 需要重新为这些顶点上色，但他正忙于修理他的时光机。幸运（或不幸）的是，现在恐龙负责处理这类任务——当然是要收费的。他需要你的帮助来找到最小花费的上色方案。因此，他给你提出了如下问题。 给定一棵有根树$^{\text{∗}}$，共有 $n$ 个顶点，顶点 $1$ 为根。每个顶点有一个整数权值 $w_i$ 和一个颜色 $c_i$，颜色是 $1$ 到 $k$ 之间的整数。然而，有些顶点失去了颜色，用 $c_i = 0$ 表示。 我们称顶点 $v$ 为 cutie，当且仅当**存在**两个顶点 $x$ 和 $y$，满足： - $\operatorname{lca}(x, y)\text{†} = v$， - $c_x = c_y$， - $c_x \neq c_v$。 树的花费定义为所有 cutie 顶点的权值之和。 你需要为所有失去颜色的顶点分配 $1$ 到 $k$ 之间的颜色，使得树的花费最小，并给出一种达到最小花费的上色方案。 $^{\text{∗}}$树是一个无环连通图。有根树是指定出一个特殊顶点作为根的树。 $\text{†}\operatorname{lca}(x, y)$ 表示 [最近公共祖先（LCA）](https://en.wikipedia.org/wiki/Lowest_common_ancestor)。

每个测试包含多组数据。第一行包含测试组数 $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$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示一条连接顶点 $u$ 和 $v$ 的边。 保证给定的边构成一棵树。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，第一行输出一个整数，表示所有合法上色方案中最小的花费。 第二行输出 $n$ 个整数 $c'_1, c'_2, \ldots, c'_n$，表示一种达到最小花费的上色方案。你需要保证： - 如果 $c_i \neq 0$，则 $c'_i = c_i$； - 如果 $c_i = 0$，则 $1 \leq c'_i \leq k$。 如果有多种最小花费的上色方案，可以输出任意一种。

在第一个测试用例中，缺失颜色有四种选择： - $c_2 = 1$ 时，没有顶点成为 cutie，花费为 $0$； - $c_2 = 2$ 时，顶点 $1$ 成为 cutie，因为 $c_2 = c_3 = 2$，$\operatorname{lca}(2, 3) = 1$ 且 $c_1 \neq 2$。因此花费为 $w_1 = 5$； - $c_2 = 3$ 时，顶点 $1$ 成为 cutie，因为 $c_2 = c_4 = 3$，$\operatorname{lca}(2, 4) = 1$ 且 $c_1 \neq 3$。因此花费为 $w_1 = 5$； - $c_2 = 4$ 时，没有顶点成为 cutie，花费为 $0$。 因此，不同上色方案的最小花费为 $0$。 在第二个测试用例中，每个顶点都有颜色，因此当前花费不可改变。由于 $c_5 = c_2 = 2$，$\operatorname{lca}(2, 5) = 1$ 且 $c_1 \neq 2$，顶点 $1$ 是 cutie，当前花费为 $w_1 = 3$。 在第三个测试用例中，下面是一种可能的最小花费上色方案：  其他一些合法的上色方案： - $c = [3, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1]$，使得顶点 $1, 2, 3, 7$ 成为 cutie： - $\operatorname{lca}(4, 8) = 1$； - $\operatorname{lca}(3, 4) = 2$； - $\operatorname{lca}(10, 11) = 3$； - $\operatorname{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$ 成为 cutie： - $\operatorname{lca}(5, 7) = 1$； - $\operatorname{lca}(5, 11) = 2$； - $\operatorname{lca}(8, 9) = 7$。 上述所有顶点与其 LCA 的颜色不同，因此花费为 $w_1 + w_2 + w_7 = 7$。 可以证明不存在花费小于 $7$ 的上色方案。 由 ChatGPT 4.1 翻译