Лабиринт Кошмаров

Автор задачи: Даниил Орешников, разработчик: Степан Мишанин

Если говорить более формально, то в задаче от нас требуется найти гамильтонов цикл в дереве, в которое добавили ребра между всеми вершинами на расстоянии не больше трёх. Очевидно, что явно построить такой граф, дополнив дерево ребрами мы не можем, ведь в худшем случае такой граф будет полным, — но для решения это и не потребуется, просто в дальнейшем будет считать, что из текущей вершины нашего дерева можно переместиться в любую вершину на расстоянии не больше трёх.

Покажем теперь, как можно в нашем дереве найти гамильтонов путь, начинающийся в корне и заканчивающийся в одном из его детей. Решать эту задачу будем рекурсивно. Пусть сейчас мы рассматриваем вершину $$$v$$$, у которой имеется $$$k$$$ детей $$$u_1, u_2, u_3, ... u_k$$$. Будем по очереди рассматривать всех её детей, тогда у нас возможны два случая:

- Если у рассматриваемой вершины $$$u_i$$$ есть дети, будем по очереди перемещаться в них (мы это можем сделать, так как расстояние между $$$v$$$ и любым ребёнком $$$u_i$$$ равно двум) и решать задачу рекурсивно для них. Напомним, что мы ищем гамильтонов цикл, начинающийся в корне и заканчивающийся в одном из его детей. Тогда, решив задачу для какого-то ребёнка $$$t_m$$$ вершины $$$u_i$$$, мы окажемся в каком-то из детей $$$t_m$$$ и можем из него переместиться в следующего ребёнка $$$u_i$$$, так как расстояние между ними будет равно трём. В конце остаётся только переместиться в вершину $$$u_i$$$, что также возможно, так как расстояние между $$$u_i$$$ и любым ребёнком её ребёнка равно двум.
- Если у рассматриваемой вершины $$$u_i$$$ нет детей, то добавим $$$u_i$$$ в ответ будто бы мы зашли в неё и продолжим рассматривать детей $$$v$$$. Тогда если у следующего ребёнка $$$u_j$$$ тоже нет детей, мы можем переместиться в него, так как расстояние между $$$u_i$$$ и $$$u_j$$$ равно двум, иначе — следуя описанному в первом пункте, мы переместимся в какого-то ребёнка $$$u_j$$$, что также возможно, так как расстояние между $$$u_i$$$ и ребёнком $$$u_j$$$ равно трём.

С помощью описанного способа найдем гамильтонов путь в нашем дереве. Так как он завершится в каком-то из детей корня, нам остаётся только переместиться из этого ребёнка в корень и мы получим требуемый в задаче цикл.