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）。

每个测试包含多组数据。第一行包含测试组数 $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 翻译