F. Максимизируем корень
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано корневое дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Вершина $$$1$$$ является корнем дерева. Каждая вершина имеет целочисленное значение. Значение $$$i$$$-й вершины равно $$$a_i$$$. Следующую операцию можно выполнить не более $$$k$$$ раз:

  • Выберите вершину $$$v$$$, которая не была выбрана ранее, и целое число $$$x$$$ такое, что $$$x$$$ является общим делителем значений всех вершин поддерева $$$v$$$. Умножьте значение каждой вершины поддерева $$$v$$$ на $$$x$$$.

Какое максимально возможное значение корневой вершины $$$1$$$ можно получить после не более чем $$$k$$$ операций? Формально, вы должны максимизировать значение $$$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$$$ и $$$v_i$$$. Гарантируется, что заданные ребра образуют дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора выведите максимальное значение корня после выполнения не более чем $$$k$$$ операций.

Пример
Входные данные
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
Выходные данные
288
576
Примечание

Оба примера имеют одно и то же дерево:

Для первого набора вы можете выполнить две операции следующим образом:

  • Выберите поддерево с вершиной $$$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$$$ и является максимальным.