给你一个有根树,由 $$$n$$$ 顶点组成,编号从 $$$1$$$ 到 $$$n$$$。顶点 $$$1$$$ 是树的根。每个顶点都有一个整数值。第 $$$i$$$ 个顶点的值为 $$$a_i$$$。您最多可以执行以下操作 $$$k$$$ 次。
- 选择一个之前没有选择过的顶点 $$$v$$$ 和一个整数 $$$x$$$,使得 $$$x$$$ 是 $$$v$$$ 子树所有顶点值的公约数。将 $$$v$$$ 子树中每个顶点的值乘以 $$$x$$$。
最多$$$k$$$操作后根节点$$$1$$$的最大可能值是多少?形式上,您必须最大化 $$$a_1$$$ 的值。
树是无环的连通无向图。有根树是具有选定顶点(称为根)的树。节点 $$$u$$$ 的子树是所有节点 $$$y$$$ 的集合,使得从 $$$y$$$ 到根的简单路径经过 $$$u$$$。请注意,$$$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$$$ 和 $$$u_i$$$ 之间的树边$$$v_i$$$。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,执行最多 $$$k$$$ 操作后输出根的最大值。
示例
输入 #1
2 5 2 24 12 24 6 12 1 2 1 3 2 4 2 5 5 3 24 12 24 6 12 1 2 1 3 2 4 2 5
输出 #1
288 576
注意
两个示例都有相同的树:
对于第一个测试用例,可以进行如下两个操作:
- 选择顶点 $$$4$$$ 和 $$$x = 2$$$ 的子树。 执行此操作后,节点值变为$$$\{24, 12, 24, 12, 12\}.$$$
- 选择顶点 $$$1$$$ 和 $$$x = 12$$$ 的子树。 执行此操作后,节点值变为$$$\{288, 144, 288, 144, 144\}.$$$
对于第二个测试用例,可以进行如下三个操作:
- 选择顶点 $$$4$$$ 和 $$$x = 2$$$ 的子树。 执行此操作后,节点值变为$$$\{24, 12, 24, 12, 12\}.$$$
- 选择顶点 $$$2$$$ 和 $$$x = 4$$$ 的子树。 执行此操作后,节点值变为$$$\{24, 48, 24, 48, 48\}.$$$
- 选择顶点 $$$1$$$ 和 $$$x = 24$$$ 的子树。 执行此操作后,节点值变为$$$\{576, 1152, 576, 1152, 1152\}.$$$