CF2252F.Spectral Components

You are given a tree consisting of $n$ vertices. Each vertex $i$ is painted with a color $c_i$.

For each distinct color $c$ present in the tree, let $m_c$ be the total number of vertices of color $c$. You are also given an array $k$ of length $n$, where $k_c$ ($1 \le k_c \le m_c$) represents the target component size for color $c$.

For every color $c$ independently, your task is to choose a connected subgraph (a component) consisting of exactly $k_c$ vertices. The vertices you choose for the component do not necessarily have to be of color $c$.

The cost of a chosen component is the sum of the shortest distances from every vertex of color $c$ to the chosen component. (The distance from a vertex $v$ to a component $S$ is defined as the minimum number of edges on a simple path from $v$ to any vertex $u$ in $S$).

For each color $c$ from $1$ to $n$, find the minimum possible cost of a valid component of size $k_c$. If there are no vertices of color $c$ in the tree, output $-1$ for that color.

给你一棵包含 $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$（$c = 1, 2, \dots, n$），求出大小为 $k_c$ 的合法连通分量的最小可能代价。若树中不存在颜色为 $c$ 的顶点，则对该颜色输出 $-1$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$) — the colors of the vertices.

The third line contains $n$ integers $k_1, k_2, \ldots, k_n$ ($1 \le k_i \le n$) — the target component sizes for each color. It is guaranteed that if color $c$ appears $m_c \gt 0$ times in the tree, then $1 \le k_c \le m_c$.

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), representing an edge between vertices $u$ and $v$. It is guaranteed that the given edges form a valid tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$），表示顶点 $u$ 与 $v$ 之间存在一条边。保证所给边构成一棵合法的树。

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

For each test case, output $n$ integers. The $c$-th integer should be the minimum possible cost of a valid component of size $k_c$ for color $c$, or $-1$ if color $c$ is not present in the tree.

对于每个测试用例，输出 $n$ 个整数。其中第 $c$ 个整数应为颜色 $c$ 的大小为 $k_c$ 的合法连通块的最小可能代价；若树中不包含颜色 $c$，则输出 $-1$。

In the first testcase, the tree has $5$ vertices. Color $1$ appears $3$ times (vertices $1, 2, 4$). Color $2$ appears $2$ times (vertices $3, 5$). Colors $3$, $4$, and $5$ do not appear, so their output is $-1$. For color $1$ ($k_1 = 2$), we can choose the component $S = {2, 4}$. The distance from vertex $1$ to $S$ is $1$. The distances from vertices $2$ and $4$ to $S$ are $0$. The total cost is $1 + 0 + 0 = 1$. For color $2$ ($k_2 = 1$), the optimal component is the single vertex $S = {2}$. The distance from $3$ to $2$ is $1$, and from $5$ to $2$ is $2$. The total cost is $3$.

In the second testcase, the tree is a star graph with center $1$ (color $2$) and $5$ leaves (color $1$). For color $1$ ($k_1 = 3$), the optimal strategy is to include the center and two leaves, for instance, $S = {1, 2, 3}$. The distances from the color $1$ leaves to $S$ are $0$ (for $2, 3$) and $1$ (for $4, 5, 6$), yielding a minimum cost of $3$. For color $2$ ($k_2 = 1$), the only vertex is the center itself. Choosing $S = {1}$ gives a cost of $0$.

In the third testcase, the tree is a line graph $1-2-3-4-5-6$ with alternating colors. For color $2$ (vertices $2, 4, 6$), we need a component of size $3$. The optimal component is $S = {3, 4, 5}$. The distances from the vertices of color $2$ to $S$ are $1$ (from $2$, via edge $2-3$), $0$ (from $4$, since it is in $S$), and $1$ (from $6$, via edge $6-5$). The total cost is $2$.

在第一个测试用例中，树包含 $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\}$；顶点 $3$ 到 $2$ 的距离为 $1$，顶点 $5$ 到 $2$ 的距离为 $2$；总代价为 $3$。

在第二个测试用例中，该树是一颗以顶点 $1$（颜色 $2$）为中心、含 $5$ 片叶子（颜色 $1$）的星形图。对于颜色 $1$（$k_1 = 3$），最优策略是选取中心及其中两片叶子，例如 $S = \{1, 2, 3\}$。所有颜色 $1$ 的叶子到 $S$ 的距离分别为：顶点 $2, 3$ 的距离为 $0$，顶点 $4, 5, 6$ 的距离为 $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$ 的距离分别为：顶点 $2$ 经边 $2-3$ 到 $S$ 的距离为 $1$，顶点 $4$ 属于 $S$ 故距离为 $0$，顶点 $6$ 经边 $6-5$ 到 $S$ 的距离为 $1$；总代价为 $2$。