Будем перебирать наибольший общий делитель $$$d$$$. Найдём все такие рёбра, что их веса делятся на $$$d$$$, такие веса будут равны: $$$d$$$, $$$2d$$$, $$$3d$$$, $$$\ldots$$$.

Для каждого $$$d$$$ выделим множество рёбер, которые разбивают исходный граф на компоненты связности. Нам нужно определить, существует ли среди этих компонент связности хотя бы одна, размер которой не меньше $$$k$$$.

Для решения этой задачи подойдёт структура данных СНМ (прочитать про неё можно на https://ru.algorithmica.org/cs/set-structures/dsu/).

Для каждого значения $$$d$$$ будем решать задачу независимо.

Будем поддерживать размер максимальной компоненты связности — $$$max\_rang$$$.

Для каждой компоненты, корень которой равен $$$v$$$, будем хранить её размер $$$rang_v$$$.

Будем по порядку объединять два множества, которые связаны ребром $$$(u, v)$$$. После объединения двух компонент, корни которых равны $$$x$$$ и $$$y$$$ соответственно ($$$x \neq y$$$), появляется новая компонента, размер которой равен $$$rang_x + rang_y$$$, зная этот размер, обновим значение $$$max\_rang$$$.

После объединения всех компонент остаётся проверить, что $$$max\_rang \geq k$$$, если это так, то обновим ответ.

Важное замечание: для каждого $$$d$$$ не нужно сохранять отдельные массивы, в которых будут храниться размеры и предки. Достаточно создать отдельный массив $$$time_v$$$, в котором будет храниться последнее $$$d$$$, при котором обновлялись значения $$$rang_v$$$, $$$p_v$$$ (где $$$p_v$$$ — предок вершины $$$v$$$). Если для текущего $$$d$$$ выполняется $$$time_v \neq d$$$, это означает, что вершина $$$v$$$ не обновлялась при текущем $$$d$$$. В таком случае нужно вернуть $$$rang_v$$$, $$$p_v$$$ к первоначальному состоянию, то есть проделать операции $$$rang_v = 1$$$, $$$p_v = v$$$.