Олимпиадный тренинг

Задача . F. Максимизируем корень

Задача

Темы: графы Деревья дп математика поиск в глубину и подобное теория чисел *2600

Вам дано корневое дерево, состоящее из $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$ операций.

Примечание

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

$\text{[math]}$

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

Выберите поддерево с вершиной $4$ и $x = 2$. $\text{[math]}$ После этой операции значения вершин станут $\{24, 12, 24, 12, 12\}.$
Выберите поддерево с вершиной $1$ и $x = 12$. $\text{[math]}$ После этой операции значения вершин станут $\{288, 144, 288, 144, 144\}.$

Значение корня равно $288$ и является максимальным.

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

Выберите поддерево с вершиной $4$ и $x = 2$. $\text{[math]}$ После этой операции значения вершин станут $\{24, 12, 24, 12, 12\}.$
Выберите поддерево с вершиной $2$ и $x = 4$. $\text{[math]}$ После этой операции значения вершин станут $\{24, 48, 24, 48, 48\}.$
Выберите поддерево с вершиной $1$ и $x = 24$. $\text{[math]}$ После этой операции значения вершин станут $\{576, 1152, 576, 1152, 1152\}.$

Значение корня равно $576$ и является максимальным.

Примеры

№	Входные данные	Выходные данные
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	288 576

time 2000 ms
memory 1024 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет