Дом в невысоком дереве

Автор задачи: Орешников Даниил, разработчик задачи: Николай Будин

Оптимальное расположение лестниц строится конструктивно. Во-первых нужно поставить $$$n$$$ лестниц между центральными комнатами на каждом этаже. Затем, пока количество оставшихся лестниц хотя бы $$$n$$$, нужно соединять лестницами все комнаты на одной вертикали. И если осталось меньше $$$n$$$ лестниц, их тоже нужно поставить на одну вертикаль подряд.

После чего, нужно посчитать ответ. Ограничения позволяют сделать это за $$$O(n^2)$$$, запустив от каждой из комнат bfs.