Moving an Edge

삭제한 간선을 $uv_1$, 새로 추가한 간선을 $uv_2$라고 하자. 여기서 $v_2$는 $uv_1$을 삭제했을 때 $v_1$이 속하는 연결 컴포넌트에 있다.

먼저 다음 두 표준화 보조정리를 사용한다.

보조정리 1

최적해 중에는 삭제한 간선과 추가한 간선이 한 끝점 $u$를 공유하는 것이 존재한다.

일반적인 연산에서 삭제한 간선을 $ab$, 추가한 간선을 $cd$라 하고, $a,c$가 같은 연결 컴포넌트에 있다고 하자. 두 컴포넌트 내부의 거리는 변하지 않는다. 서로 다른 컴포넌트의 정점 $x,y$에 대해서만

$$\operatorname{dist}(x,c)-\operatorname{dist}(x,a) + \operatorname{dist}(d,y)-\operatorname{dist}(b,y)$$

의 값이 $0$인지 확인하면 된다.

각 차이는 대응하는 두 정점을 잇는 경로를 따라 일정하게 증가하거나 감소하며, 경로에 붙은 서브트리에서는 같은 값을 가진다. 두 경로의 값 구간을 겹치는 순서대로 비교하고, 처음과 마지막으로 상쇄되는 층을 기준으로 간선을 옮기면 한쪽 새 끝점을 원래 끝점으로 바꾸어도 변화한 쌍의 수가 증가하지 않는다. 이 과정을 반복하면 한 끝점을 공유하는 최적해를 얻는다.

보조정리 2

$u$가 리프가 아니라면 $\operatorname{dist}(v_1,v_2)\le2$인 최적해가 존재한다.

$\operatorname{dist}(v_1,v_2)\ge3$인 연산을 생각하자. $v_1$과 사이 경로의 양쪽 끝 방향 컴포넌트에서 가장 가까운 리프를 택해 같은 중간 지점을 기준으로 옮길 수 있다. 이 리프 이동에서 변화하는 쌍은 원래 연산에서 변화하는 서로 다른 컴포넌트 쌍의 한 층에 포함된다. 가 리프가 아니므로 쪽 컴포넌트의 크기는 이상이고, 원래 연산의 변화량은 이 층의 크기만큼을 적어도 두 번 포함한다. 따라서 리프 이동이 더 나쁘지 않다.

이제 한 끝점을 공유하는 연산만 계산한다.

$uv_1$을 삭제했을 때 $u$가 속하는 컴포넌트를 $A$, 다른 컴포넌트를 $B$라 하고 $|A|=a$라 하자. 내부와 내부의 거리는 변하지 않는다. , 에 대해서는

$$\begin{align*} \operatorname{dist}_T(x,y) &=\operatorname{dist}(x,u)+1+\operatorname{dist}(v_1,y),\\ \operatorname{dist}_{T'}(x,y) &=\operatorname{dist}(x,u)+1+\operatorname{dist}(v_2,y). \end{align*}$$

따라서 $y$에 대한 두 거리의 비교 결과가 $A$의 모든 $x$에 똑같이 적용된다.

$\operatorname{dist}(v_1,v_2)$가 홀수이면 두 정점에서 같은 거리에 있는 정점이 없다. 이때 변화량은

$$a|B|$$

이다.

거리가 짝수이면 경로의 가운데 정점을 $m$이라 하자. $v_1$과 $v_2$에서 같은 거리에 있는 정점은 $m$에서 경로의 두 방향 간선을 제거했을 때 이 속하는 컴포넌트에 정확히 포함된다. 두 경로 방향의 컴포넌트 크기를 라 하면 변화량은

$$a(p+q)$$

이다.

거리 1인 경우

경로가 $u-v_1-v_2$라고 하자. $u$ 방향 컴포넌트의 크기를 $a$라 하면 변화량은

$$a(N-a)$$

이다.

$v_1$의 각 이웃 방향 컴포넌트 크기 중 하나를 $a$로 고를 수 있다. 함수 $a(N-a)$는 오목한 이차식이므로, 가능한 $a$ 중 최솟값과 최댓값만 확인하면 된다.

거리 2인 경우

경로가

$$u-v_1-m-v_2$$

라고 하자.

$m-v_1$을 제거했을 때 $v_1$ 쪽 컴포넌트 크기를 $S$라 하자. 에서 방향 컴포넌트 크기를 , 에서 방향 컴포넌트 크기를 라 하면 변화량은

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

이다.

고정된 방향 간선 $v_1\to m$에 대해 $b$는 가능한 값 중 최솟값을 고르면 된다. $a(S+b-a)$도 오목한 이차식이므로, 방향을 제외한 컴포넌트 크기의 최솟값과 최댓값만 확인하면 된다.

각 정점에서 이웃 방향 컴포넌트 크기의 작은 값 두 개와 큰 값 두 개를 저장하면 모든 후보를 $O(N)$에 계산할 수 있다.

리프를 옮기는 경우

이제 $u$가 리프인 경우에는 $v_1$과 $v_2$의 거리가 길 수 있다.

거리가 홀수이면 $u$와 나머지 $N-1$개 정점 사이의 거리가 모두 변한다. 따라서 변화량은 $N-1$이다. 이는 항상 가능한 기본 상한이다.

거리가 $2t$이면 가운데 정점을 $m$이라 하자. $m$에서 $u$ 방향의 가지를 $X$, $v_2$ 방향의 가지를 라 하고 크기를 각각 라 하자. 와의 거리가 변하는 정점은 에서 를 제외한 정점과 의 정점뿐이다. 변화량은

$$s_X+s_Y-1$$

이다.

$m$의 각 이웃 방향 가지에 대해 다음 값을 정의한다.

• $s$: 가지의 정점 수.
• $h$: $m$에서 가지 안의 가장 먼 정점까지의 거리.
• $\ell$: $m$에서 가지 안의 가장 가까운 원래 트리의 리프까지의 거리.

가지 $X$가 기존 리프가 있는 방향이 되려면 $\ell\ge2$여야 한다. 가장 가까운 리프를 $u$로 고르면 $t=\ell-1$이다. 다른 가지 $Y$는 깊이 의 정점을 포함해야 하므로

$$h_Y\ge\ell_X-1$$

을 만족해야 한다.

따라서 각 가지 $X$에 대해 다음 질의를 계산하면 된다.

높이가 $\ell_X-1$ 이상인 다른 가지 중 크기의 최솟값

모든 방향 간선에 대한 $s,h,\ell$은 재루팅 DP로 구한다. 한 방향 간선의 컴포넌트 정보를 반대쪽 정점으로 전달하는 메시지에 컴포넌트 크기, 최대 깊이, 가장 가까운 리프 거리를 저장하면 된다.

각 정점별 질의를 정렬하면 $O(N\log N)$이지만, 높이와 리프 거리는 모두 $0$ 이상 $N$ 이하의 정수이다. 모든 가지를