Maximizing Root
Contest: Codeforces Round 848 (Div. 2)
Difficulty rating: 2600
Tags: dfs and similar, dp, graphs, math, number theory, trees

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

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
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\}.$$$

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

Example input:
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

Example output:
288
576

Editorial:
Let, $$$x_u$$$ be the value of node $$$u$$$ and $$$dp[u][d]$$$ be the minimum number of moves required to make the GCD of the subtree of $$$u$$$ equal to a multiple of $$$d$$$.
Now, $$$dp[u][d] = 0$$$ if the subtree GCD of node $$$u$$$ is already a multiple of $$$d$$$ and $$$dp[u][d] = \infty$$$ if $$$(x_u \cdot x_u)$$$ is not a multiple of $$$d$$$.
For each divisor $$$y$$$ of $$$d$$$, suppose, we want to perform the move on the subtree of $$$u$$$ by multiplying each node value of the subtree with $$$y$$$ iff $$$(x_u\cdot y)$$$ is a multiple of $$$d$$$ and $$$y$$$ is a divisor of $$$x_u$$$. In this case, we have to make the GCD of all the subtree of child nodes of $$$u$$$ equal to a multiple of $$$LCM(\frac{d}{y}, y)$$$ before performing the move on the subtree of $$$u$$$. This is because we have to make each node of the subtree a multiple of $$$\frac{d}{y}$$$ to get the multiple of $$$d$$$ after performing the move on the subtree of node $$$u$$$ using $$$y$$$. Also, to perform the move of multiplying by $$$y$$$, the value of each subtree node should be a multiple of $$$y$$$. So we have to make each node value a multiple of $$$LCM(\frac{d}{y}, y)$$$.
So, $$$dp[u][d]$$$ will be calculated from $$$dp[v][LCM(\frac{d}{y}, y)]$$$ for each divisor $$$y$$$ of $$$d$$$ for all child $$$v$$$ of $$$u$$$.
Now, $$$x_1\cdot D$$$ is the answer where $$$D$$$ is the largest divisor of $$$x_1$$$ such that $$$k \geq dp[1][D]$$$.
Time Complexity: $$$O(n\cdot m^2)$$$ where $$$m$$$ is the number of divisors of $$$x_1$$$.