CF1778F.Maximizing Root

You are given a rooted tree consisting of $n$ vertices numbered from $1$ to $n$. Vertex $1$ is the root of the tree. Each vertex has an integer value. The value of $i$-th vertex is $a_i$. You can do the following operation at most $k$ times.

• Choose a vertex $v$ that has not been chosen before and an integer $x$ such that $x$ is a common divisor of the values of all vertices of the subtree of $v$. Multiply by $x$ the value of each vertex in the subtree of $v$.

What is the maximum possible value of the root node $1$ after at most $k$ operations? Formally, you have to maximize the value of $a_1$.

A tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root. The subtree of a node $u$ is the set of all nodes $y$ such that the simple path from $y$ to the root passes through $u$. Note that $u$ is in the subtree of $u$.

你被给定一棵包含 $n$ 个顶点的有根树，顶点编号从 $1$ 到 $n$。顶点 $1$ 是该树的根。每个顶点都有一个整数值，其中第 $i$ 个顶点的值为 $a_i$。你最多可以执行以下操作 $k$ 次：

• 选择一个此前未被选过的顶点 $v$，以及一个整数 $x$，使得 $x$ 是 $v$ 的子树中所有顶点的值的一个公因数；然后将 $v$ 的子树中每个顶点的值都乘以 $x$。

在最多执行 $k$ 次操作后，根节点 $1$ 的值 $a_1$ 的最大可能值是多少？形式上，你需要最大化 $a_1$ 的值。

树是一种无环的连通无向图。有根树是一棵选定某个顶点作为根的树。节点 $u$ 的子树是指所有满足“从 $y$ 到根的简单路径经过 $u$”的节点 $y$ 所构成的集合。注意：$u$ 自身属于其子树。

The first line contains an integer $t$ ($1 \leq t \leq 50\,000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $0 \leq k \leq n$) — the number of vertices in the tree and the number of operations.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 1000$), where $a_i$ denotes the value of vertex $i$.

Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$), denoting the edge of the tree between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

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

第一行包含一个整数 $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$。

For each test case, output the maximum value of the root after performing at most $k$ operations.

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

Both examples have the same tree:

For the first test case, you can do two operations as follows:

• Choose the subtree of vertex $4$ and $x = 2$.

  

  After this operation, the node values become ${24, 12, 24, 12, 12}.$

• Choose the subtree of vertex $1$ and $x = 12$.

  

  After this operation, the node values become ${288, 144, 288, 144, 144}.$

The value of the root is $288$ and it is the maximum.

For the second test case, you can do three operations as follows:

• Choose the subtree of vertex $4$ and $x = 2$.

  

  After this operation, the node values become ${24, 12, 24, 12, 12}.$

• Choose the subtree of vertex $2$ and $x = 4$.

  

  After this operation, the node values become ${24, 48, 24, 48, 48}.$

• Choose the subtree of vertex $1$ and $x = 24$.

  

  After this operation, the node values become ${576, 1152, 576, 1152, 1152}.$

The value of the root is $576$ and it is the maximum.

两个示例具有相同的树：

对于第一个测试用例，你可以执行如下两次操作：

• 选择顶点 $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$，且这是最大值。