Развитие города

Построим «дерево поддеревьев» $$$F$$$. Корневым поддеревом будет исходное дерево, а при каждом подвешивании мы создадим вершину для нового поддерева, и подвесим её в дереве $$$F$$$ к тому поддереву, к вершине которого мы подвешиваем поддерево в исходном дереве. Длину ребра в дереве $$$F$$$ установим равной глубине вершины, к которой происходит подвешивание, относительно корня её поддерева, плюс один.

Как теперь вычислить глубину вершины $$$v$$$ в дереве после всех подвешиваний? Найдём соответствующую ей вершину в $$$F$$$ (поддерево исходного дерева). Сумма длин ребёр на пути от этой вершины до корня в $$$F$$$ плюс глубина вершины $$$v$$$ в исходном дереве относительно корня её поддерева — это и есть то, что нам нужно.

Как найти наименьшего общего предка вершин $$$v$$$ и $$$u$$$ после всех подвешиваний? Найдём соответствующие им вершины в $$$F$$$ и найдём их наименьшего общего предка $$$z$$$ (здесь $$$z$$$ — это вершина $$$F$$$, соответствующая некоторому поддереву исходного дерева). Найдём, к каким вершинам поддерева $$$z$$$ были подвешены те части дерева, в которых находились вершины $$$v$$$ и $$$u$$$. Найдём наименьшего общего предка найденных двух вершин в исходном дереве. Его копия в поддереве $$$z$$$ — это и есть то, что нам нужно.

Умея находить глубину и наименьшего общего предка, можно вычислить расстояние между вершинами $$$v$$$ и $$$u$$$ как сумму их глубин минус удвоенная глубина их наименьшего общего предка.