Maximizing Root

题意翻译

你有一颗有根树，有 $n$ 个节点，编号为 $1 \sim n$。 第 $i$ 个顶点的权值是 $a_i$，你可以进行以下操作： + 选择一个之前没选过的节点 $v$，以及一个正整数 $x$，需要满足 $x$ 是 $v$ 子树内所有点的权值的公约数，然后令所有 $v$ 子树内的节点的权值都乘 $x$。 问在操作 $\le k$ 次后 $a_1$ 的最大可能值是多少？ Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #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

说明

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.

题目大意：
你有一棵有根树，有 $n$ 个节点，编号为 $1 \sim n$。第 $i$ 个顶点的权值是 $a_i$，你可以进行以下操作：

+ 选择一个之前没选过的节点 $v$，以及一个正整数 $x$，需要满足 $x$ 是 $v$ 子树内所有点的权值的公约数，然后令所有 $v$ 子树内的节点的权值都乘 $x$。

问在操作 $\le k$ 次后 $a_1$ 的最大可能值是多少？

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $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$ 次操作后根节点的最大值。题目大意： 你有一棵有根树，有 $n$ 个节点，编号为 $1 \sim n$。第 $i$ 个顶点的权值是 $a_i$，你可以进行以下操作： + 选择一个之前没选过的节点 $v$，以及一个正整数 $x$，需要满足 $x$ 是 $v$ 子树内所有点的权值的公约数，然后令所有 $v$ 子树内的节点的权值都乘 $x$。 问在操作 $\le k$ 次后 $a_1$ 的最大可能值是多少？ 输入输出数据格式： 输入格式： - 第一行包含一个整数 $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$ 次操作后根节点的最大值。