Moving an Edge

By the standard endpoint-normalization and long-move exchange lemmas, an optimum exists in one of the following forms.

• The deleted and added edges share one endpoint $u$.
• If $u$ is not a leaf, the old and new attachment vertices are at distance at most $2$.
• If $u$ is a leaf, the new attachment vertex may be arbitrarily far away.

Delete $uv_1$ and add $uv_2$. Let $A$ be the component containing $u$ after the deletion, and let $|A|=a$. Distances inside either component do not change. For every $x\in A$ and every vertex $y$ in the other component, the distance changes exactly when

$$\operatorname{dist}(v_1,y)\ne\operatorname{dist}(v_2,y).$$

If $\operatorname{dist}(v_1,v_2)$ is odd, every such $y$ changes. If it is even, only the two path-direction branches at the midpoint contribute.

For distance $1$, the cost is $a(N-a)$. For distance $2$, along the path $u-v_1-m-v_2$, let $S$ be the size of the $v_1$ side of $v_1m$, let $a$ be the size of the $u$ branch at $v_1$, and let $b$ be the size of the $v_2$ branch at $m$. The cost is

$$a(S-a+b).$$

Both expressions are concave in $a$, so only the minimum and maximum available branch sizes are needed. Keeping the two smallest and two largest branch sizes at every vertex handles all distance-$1$ and distance-$2$ candidates in linear time.

For a leaf move with an even old-to-new attachment distance, let $m$ be the midpoint. Let $X$ be the branch containing the moved leaf and $Y$ the branch containing the new attachment vertex. The cost is

$$s_X+s_Y-1.$$

For every directed branch from a center vertex, compute its size $s$, maximum depth $h$, and nearest original-leaf distance $\ell$. Branch $X$ is usable when $\ell\ge2$, and another branch $Y$ is usable when

$$h_Y\ge\ell_X-1.$$

Thus each branch asks for the minimum size of another branch whose height is at least a threshold.

All directed-branch values are computed with rerooting DP. Sort branch records by center and decreasing height, and sort queries by center and decreasing threshold. Since every key is an integer between $0$ and $N$, stable counting sort makes both orderings linear. During the sweep, maintain the two smallest active branch sizes so that the query branch itself can be excluded.

The total time complexity is $O(N)$ and the memory complexity is $O(N)$.

Solution written by GPT5.6