CF1778F Maximizing Root

给定一棵有 $n$ 个顶点的有根树，顶点编号为 $1$ 到 $n$，顶点 $1$ 是树的根。每个顶点有一个整数值，第 $i$ 个顶点的值为 $a_i$。你最多可以进行 $k$ 次如下操作： - 选择一个之前未被选择过的顶点 $v$，以及一个整数 $x$，其中 $x$ 是 $v$ 的子树中所有顶点值的公约数。将 $v$ 的子树中每个顶点的值都乘以 $x$。 请问，最多进行 $k$ 次操作后，根节点 $1$ 的最大可能值是多少？即最大化 $a_1$ 的值。 一棵树是一个无环连通无向图。有根树是指定了一个根节点的树。节点 $u$ 的子树是所有满足从 $y$ 到根的简单路径经过 $u$ 的节点 $y$ 的集合。注意 $u$ 也在 $u$ 的子树中。

第一行包含一个整数 $t$（$1 \leq t \leq 50\,000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$0 \leq k \leq n$），分别表示树的顶点数和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 1000$），其中 $a_i$ 表示第 $i$ 个顶点的值。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$），表示树中顶点 $u_i$ 和 $v_i$ 之间有一条边。保证给出的边构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出在最多进行 $k$ 次操作后根节点的最大可能值。

两个样例的树结构相同：  对于第一个测试用例，你可以进行如下两次操作： - 选择顶点 $4$ 的子树，$x=2$。 操作后，节点值变为 $\{24, 12, 24, 12, 12\}$。 - 选择顶点 $1$ 的子树，$x=12$。 操作后，节点值变为 $\{288, 144, 288, 144, 144\}$。 此时根节点的值为 $288$，且为最大值。 对于第二个测试用例，你可以进行如下三次操作： - 选择顶点 $4$ 的子树，$x=2$。 操作后，节点值变为 $\{24, 12, 24, 12, 12\}$。 - 选择顶点 $2$ 的子树，$x=4$。 操作后，节点值变为 $\{24, 48, 24, 48, 48\}$。 - 选择顶点 $1$ 的子树，$x=24$。 操作后，节点值变为 $\{576, 1152, 576, 1152, 1152\}$。 此时根节点的值为 $576$，且为最大值。 由 ChatGPT 4.1 翻译