CF2252F Spectral Components

给定一棵包含 $n$ 个节点的树。每个节点 $i$ 被涂上了颜色 $c_i$。 对树中出现的每种不同颜色 $c$，记 $m_c$ 为颜色 $c$ 的节点总数。还给定一个长度为 $n$ 的数组 $k$，其中 $k_c$（$1 \le k_c \le m_c$）表示颜色 $c$ 需要选择的连通块大小。 对于每种颜色 $c$（互不影响），你需要选择一个恰好包含 $k_c$ 个节点的连通子图（连通块）。选中的连通块中的节点不要求全为颜色 $c$。 所选连通块的代价定义为：树中每一个颜色为 $c$ 的节点到该连通块的最短距离之和（某个节点 $v$ 到连通块 $S$ 的距离定义为 $v$ 到 $S$ 中任意节点 $u$ 的最短路径上的最少边数的最小值）。 对于每种颜色 $c$（$1$ 到 $n$），输出一个大小为 $k_c$ 的合法连通块的最小可能代价。如果颜色 $c$ 在树中没有出现，则输出 $-1$。

每个测试点包含多组测试数据。第一行输入测试组数 $t$（$1 \le t \le 10^4$）。 每组测试用例的第一行输入一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示树的节点数。 第二行输入 $n$ 个整数 $c_1, c_2, \ldots, c_n$，表示每个节点的颜色（$1 \le c_i \le n$）。 第三行输入 $n$ 个整数 $k_1, k_2, \ldots, k_n$，表示每种颜色的目标连通块大小（$1 \le k_i \le n$）。保证如果颜色 $c$ 在树中出现过 $m_c > 0$ 次，则 $1 \le k_c \le m_c$。 接下来的 $n-1$ 行，每行两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示树上的一条边。 保证给定的边能够构成一棵合法的树。 并且所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出 $n$ 个整数，第 $c$ 个数为颜色 $c$、连通块大小为 $k_c$ 时的最小可能代价。如果颜色 $c$ 在树中不存在，输出 $-1$。

在第一个测试用例中，树有 $5$ 个节点。颜色 $1$ 出现了 $3$ 次（节点 $1, 2, 4$），颜色 $2$ 出现了 $2$ 次（节点 $3, 5$），颜色 $3, 4, 5$ 没有出现，因此它们的输出是 $-1$。对于颜色 $1$（$k_1=2$），我们可以选择连通块 $S=\{2,4\}$，节点 $1$ 到 $S$ 的距离是 $1$，$2$ 和 $4$ 到 $S$ 的距离都是 $0$，总代价为 $1+0+0=1$。对于颜色 $2$（$k_2=1$），最优方案是选择单个节点 $S=\{2\}$，颜色 $2$ 的节点 $3$ 到 $2$ 距离 $1$，$5$ 到 $2$ 距离 $2$，总代价为 $3$。 在第二个测试用例中，树为星形图，中心点 $1$（颜色 $2$），叶子点 $5$ 个（颜色 $1$）。对于颜色 $1$（$k_1=3$），可以选择中心点和两个叶子，例如 $S=\{1,2,3\}$。将 $2,3$ 作为连通块中的颜色 $1$ 节点，则 $4,5,6$ 到 $S$ 的距离为 $1$，总代价为 $3$。对于颜色 $2$（$k_2=1$），只有中心点本身，选择 $S=\{1\}$，总代价为 $0$。 在第三个测试用例中，树为链式结构 $1-2-3-4-5-6$，颜色交错。对于颜色 $2$（节点 $2,4,6$），连通块大小为 $3$，可以选 $S=\{3,4,5\}$。$2$ 到 $S$ 距离 $1$（经 $2-3$），$4$ 到 $S$ 距离 $0$（自身选入），$6$ 到 $S$ 距离 $1$（经 $6-5$），总代价 $2$。 由 ChatGPT 5 翻译