Let's fix some vertex $$$v$$$ for which the answer is being calculated. Suppose the degree of the vertex $$$v$$$ in the tree is $$$deg_v$$$, then it's clear that it's necessary to add $$$deg_v - 1$$$ edges. Consider the components that appear after removing $$$v$$$. Then, the goal is to use the new edges to unite all the components into one, using the minimum total cost. This is the same as finding the minimum spanning tree in a graph, where the vertices are the components that resulted from removing $$$v$$$, and for every $$$a, b$$$, an edge with a weight of $$$|a - b|$$$ is drawn between the components containing $$$a$$$ and $$$b$$$.
Let's simulate Kruskal's algorithm for this graph. Consider all the single-weight edges in this graph: $$$(1, 2), (2, 3), ..., (v - 2, v - 1), (v + 1, v + 2), ..., (n - 1, n)$$$. It's clear that using the single-weight edges, the vertices with numbers $$$[1, v - 1]$$$ will definitely end up in one component, and the vertices with numbers $$$[v + 1, n]$$$ will also end up in one component. To unite these two components, it would be optimal to add an edge $$$(v - 1, v + 1)$$$.
It turns out that it's sufficient to consider only all the single-weight edges and the edge $$$(v - 1, v + 1)$$$. Let's limit the number of single-weight edges to $$$O(deg_v)$$$. For this, in each component $$$u$$$, calculate $$$mn_u$$$ and $$$mx_u$$$ — the minimum and maximum in the component, respectively. Claim: among the single-weight edges, it's sufficient to consider edges of the form $$$(mn_u, mn_u - 1)$$$, $$$(mx_u, mx_u + 1)$$$.
ProofFirst, understand when it's necessary to add the edge $$$(v - 1, v + 1)$$$. Note that if there's at least one component $$$u$$$ such that $$$mn_u < v < mx_u$$$, then the edge $$$(v - 1, v + 1)$$$ won't be needed; otherwise, it will be. This is quite easy to show by simulating Kruskal's algorithm.
Let $$$v = 1$$$. We'll show that using edges $$$(mn_u, mn_u - 1)$$$, all components will unite. Go through the vertices $$$x$$$ from $$$2$$$ to $$$n$$$ and maintain the invariant that all vertices from $$$2$$$ to $$$x$$$ are in one component. At $$$x = 2$$$, this holds. When $$$x$$$ is the minimum in some component, then the edge $$$(x - 1, x)$$$ will be added, and since $$$x - 1$$$ is in one component with $$$2$$$, $$$x$$$ will now also be. When $$$x$$$ is not the minimum in some component, then $$$mn$$$ — the minimum in the component $$$x$$$ will be in one component with $$$2$$$ ($$$mn < x$$$, the invariant holds), meaning $$$x$$$ will also be in one component with $$$2$$$. Thus, it turns out that all will be in one component.
Now consider an arbitrary $$$v$$$. Separately consider the prefix of vertices $$$[1, v - 1]$$$ and the suffix $$$[v + 1, n]$$$. Then, similarly to $$$v = 1$$$, it can be shown that for the prefix of vertices $$$[1, v - 1]$$$, using edges of the form $$$(mn_u, mn_u - 1)$$$, you can unite $$$[1, v - 1]$$$. Similarly, for the suffix of vertices $$$[v + 1, n]$$$, using edges of the form $$$(mx_u, mx_u + 1)$$$, you can unite $$$[v + 1, n]$$$.
Now, if the edge $$$(v - 1, v + 1)$$$ is necessary, then add it to the answer. Otherwise, there's at least one component $$$u$$$ such that $$$mn_u < v < mx_u$$$, meaning the prefix of vertices $$$[1, v - 1]$$$ and the suffix $$$[v + 1, n]$$$ will unite into one component.
Finding $$$mn_u$$$, $$$mx_u$$$ for each component is straightforward; what remains is to determine which components are connected by the edges $$$(mn_u, mn_u - 1)$$$, $$$(mx_u, mx_u + 1)$$$. This can be done with binary search through the Euler tour of the tree. After that, Kruskal's algorithm can be initiated to calculate the answer.
Let's estimate the time complexity. For a specific vertex $$$v$$$, the time complexity will be $$$deg_v \cdot \log n$$$, so the total time complexity is $$$O(n \cdot \log n)$$$.
Depending on the implementation of the last step, the problem can be solved in $$$O(n)$$$, $$$O(n \cdot \alpha(n))$$$, where $$$\alpha(n)$$$ is the inverse Ackermann function relative to $$$n$$$.