Я получил вопрос в конкурсе (который закончился несколько недель назад).Вопрос, который я интерпретировал, был:
1002
Учитывая неориентированный ациклический граф, который связан (N-1) ребрами и N узлами.Граф гарантированно будет подключен.Для двух узлов u и v необходимо найти два узла x и y графика, чтобы путь между этими двумя узлами полностью перекрывал путь между заданными городами u и v, а gcd (x, y) максимально возможен.
Ограничения
1 <= N <= 5 * 10 ^ 5 </p>
1 <= a, b, u, v <= N </p>
где a, b - два произвольных узла в графе.
Пример: пусть граф имеет 10 узлов (от 1 до 10)
Теперь в предыдущей строке я дам два целых числа a и bэто означает, что a и b напрямую связаны.
1 4
1 5
1 2
4 3
4 6
5 7
2 10
2 9
2 8
Наконец uv 4 2
Ans -4
Путь от u к v равен 4 -> 1 -> 2
Теперь некоторые пути, которые полностью перекрывают путь от u к v:
4 -> 1 -> 2 -> 10
3 -> 4 -> 1 -> 2 -> 9
4 -> 1 -> 2 -> 8
и так далее ...
Примечаниечто выбор пути от 4 до 8 полностью перекрывает путь u к v, а также gcd (4,8) = 4, что является максимально возможным.
График: https://i.stack.imgur.com/Phkwi.png 
Ограничение времени: 3,0 с
Мой подход к решению проблемы был следующим:
Найти путь от каждого узла до каждого другого узла и сохранить его в списке массивов.
Переберите все списки и найдите, содержатся ли пути u и v в массиве.
Если путь найден, вычислите gcd начального и конечного узла и проверьте максимальный gcd.
Однако я думаю, что мой подход слишком груб, а код слишком длинный, и мне кажется, что он слишком сложен.
Может кто-нибудь предложить какое-либо предложение или подход для решения этого вопроса?