Зафиксируем какую-то вершину $$$v$$$, для которой считается ответ. Пусть степень вершины $$$v$$$ в дереве $$$deg_v$$$, тогда понятно, что нужно добавить $$$deg_v - 1$$$ ребер. Рассмотрим компоненты, которые появляются после удаления $$$v$$$. Тогда хочется используя новые ребра объединить все компоненты одну, используя минимальную суммарную стоимость. Это тоже самое, что и найти минимальное остовное дерево в графе, где вершины это компоненты, который получились после удаления $$$v$$$, и для каждых $$$a, b$$$ проведено ребро весом $$$|a - b|$$$ между компонентами, содержащих $$$a$$$ и $$$b$$$.
Давайте симмулировать алгоритм Крускала для этого графа. Рассмотрим все единичные ребра в этом графе: $$$(1, 2), (2, 3), ..., (v - 2, v - 1), (v + 1, v + 2), ..., (n - 1, n)$$$. Понятно, что используя единичные ребра вершины с номерами $$$[1, v - 1]$$$ точно окажутся в одной компоненте, и вершины с номерами $$$[v + 1, n]$$$ тоже окажутся в одной компоненты. Чтобы объединить эти две компоненты, оптимально будет добавить ребро $$$(v - 1, v + 1)$$$.
Получается, что достаточно рассматривать только все единичные ребра и ребро $$$(v - 1, v + 1)$$$. Давайте ограничим количество единичных ребер до $$$O(deg_v)$$$. Для этого посчитаем в каждой компоненте $$$u$$$ $$$mn_u$$$ и $$$mx_u$$$ — минимум и максимум в компоненте соотвественно. Утверждение: среди единичных ребер достаточно рассматривать ребра вида $$$(mn_u, mn_u - 1)$$$, $$$(mx_u, mx_u + 1)$$$.
ДоказательствоСначала поймем, когда нужно добавлять ребро $$$(v - 1, v + 1)$$$. Заметим, что если есть хотя бы одна компонента $$$u$$$ такая, что $$$mn_u < v < mx_u$$$, то ребро $$$(v - 1, v + 1)$$$ не понадобится, а иначе понадобится. Это достаточно легко показать, симмулируя алгоритм Крускала.
Пусть $$$v = 1$$$. Покажем, что используя ребра $$$(mn_u, mn_u - 1)$$$ все компоненты объединятся. Будем идти по вершинам $$$x$$$ от $$$2$$$ до $$$n$$$ и поддерживать инвариант, что все вершины от $$$2$$$ до $$$x$$$ лежат в одной компоненте. При $$$x = 2$$$ выполняется. Когда $$$x$$$ — минимум в какой-то компоненте, то добавится ребро $$$(x - 1, x)$$$ и поскольку $$$x - 1$$$ лежит в одной компоненте с $$$2$$$, то $$$x$$$ теперь тоже будет. Когда $$$x$$$ не является минимумом в какой-то компоненте, то $$$mn$$$ — минимум в компоненте $$$x$$$ будет лежать в одной компоненте с $$$2$$$ ($$$mn < x$$$, выполняется инвариант), а значит и $$$x$$$ тоже будет в одной компоненте с $$$2$$$. Итого получится, что все будут лежат в одной компоненте.
Рассмотрим теперь произвольное $$$v$$$. Отдельно рассмотрим префикс вершин $$$[1, v - 1]$$$ и суффикс $$$[v + 1, n]$$$. Тогда аналогично $$$v = 1$$$ можно показать, что для префикса вершин $$$[1, v - 1]$$$, используя ребра вида $$$(mn_u, mn_u - 1)$$$, можно объединить $$$[1, v - 1]$$$. Также и для суффикса вершин $$$[v + 1, n]$$$, используя ребра вида $$$(mx_u, mx_u + 1)$$$, можно объединить $$$[v + 1, n]$$$.
Теперь если ребро $$$(v - 1, v + 1)$$$ необходимо, то добавим его в ответ. Иначе есть хотя бы одна компонента $$$u$$$ такая, что $$$mn_u < v < mx_u$$$, а значит префикс вершин $$$[1, v - 1]$$$ и суффикс $$$[v + 1, n]$$$ объединятся в одну компоненту.
Найти для каждой компоненты $$$mn_u$$$, $$$mx_u$$$ нетяжело, осталось для вершины $$$v$$$ находить какие компоненты соединяют ребра $$$(mn_u, mn_u - 1)$$$, $$$(mx_u, mx_u + 1)$$$. Это можно делать бинпоиском по эйлеровому обходу дерева. После чего можно запустить алгоритм Крускала и посчитать ответ.
Оценим время работы. Для конкретной вершины $$$v$$$ время работы будет $$$deg_v \cdot \log n$$$, а значит суммарное время работы $$$O(n \cdot \log n)$$$.
В зависимости от реализации последнего шага можно решать задачу за $$$O(n)$$$, $$$O(n \cdot \alpha(n))$$$, где $$$\alpha (n)$$$ — обратная функция Аккермана к числу $$$n$$$.