Нюхли

Заметим, что описанная в условии конструкция представляет из себя граф, а именно — дерево. А две искомые вершины это его листы.

С помощью поиска в глубину, найдем для каждой вершины наименее глубокий лист среди ее потомков. Для это корнем дерева нужно взять не лист (число соседей больше одного).

Рассмотрим пути между листами. Утверждение: такой путь единственен (дерево) и сначала идет вверх до какого-то предка (наименьшего общего предка двух листов), а потом идет вниз, до второго листа.

Таким образом можно найти для каждой вершины два наименее удаленных друг от друга листа, путь между которыми «перегибается» в ней. Для этого посмотрим уже посчитанные наименее глубокие листы по каждому ребенку и если детей хотя бы два, то ответ это сумма расстояний до найденных листов.

Ответом же на задачу будет минимум по всем вершинам из найденных наименьших расстояний. Итоговая сложность O($$$n$$$).

Замечание: возможна сложность O($$$n \log n$$$), если для упрощения поиска двух минимумов из детей использовать быструю сортировку.