Identity

서로 다른 두 정점 $u,v$에 대하여

$$\delta(u,v)=\max(1,d_T(u,v))$$

라고 하자. $\delta$는 삼각 부등식을 만족한다.

좌표가 증가하는 순서대로 정점을 $p_1,p_2,\ldots,p_N$이라 하자. 인접한 두 정점의 좌표 차이는 적어도 $$이므로 배치의 길이는

$$\sum_{i=1}^{N-1}\delta(p_i,p_{i+1})$$

이상이다. 반대로 위 값들을 차례대로 좌표 차이로 사용하면, 삼각 부등식에 의해 모든 두 정점에 대한 조건을 만족한다. 따라서 문제는 거리 $\delta$에서 가장 짧은 해밀턴 경로의 길이를 구하는 것과 같다.

가중치가 $0$인 간선으로 연결된 정점들을 하나의 컴포넌트로 합치자. 합친 트리를 $H$라고 하자. $H$의 모든 간선 가중치는 $1$이다. $H$의 정점 $v$가 나타내는 원래 정점의 수를 $c_{}$, 에서의 차수를 라고 하자.

서로 다른 컴포넌트에 속한 두 원래 정점 사이의 $\delta$ 거리는 $H$에서의 거리이고, 같은 컴포넌트에 속한 두 원래 정점 사이의 거리는 $1$이다.

원래 정점들의 순서를 따라 서로 다른 컴포넌트 사이의 이동을 $H$ 위의 경로로 펼치면, $H$의 모든 정점을 방문하는 하나의 보행을 얻는다. 시작 컴포넌트를 $s$, 마지막 컴포넌트를 $t$라 하자. $s$와 $t$ 사이의 경로를 $P$라고 하면, 위의 간선은 적어도 한 번, 나머지 간선은 적어도 두 번 지나야 한다.

한 간선을 최소 횟수보다 두 번 더 지나는 것은 이동 길이를 $2$ 늘리고, 양 끝 컴포넌트에서 사용할 수 있는 방문 횟수를 각각 최대 한 번 늘린다. 같은 컴포넌트의 남은 정점을 연속으로 배치하는 비용도 정점 하나당 $1$이므로, 간선을 추가로 왕복해도 답은 감소하지 않는다. 따라서 $P$의 간선은 한 번, 나머지 간선은 두 번 지나는 보행만 고려하면 충분하다.

이 보행에서 컴포넌트 $v$의 방문 횟수는 다음과 같다.

• $v$가 $P$의 내부 정점이면 $\deg(v)-1$번이다.
• 그 외에는 $\deg(v)$번이다.

한 번 방문할 때 그 컴포넌트의 원래 정점을 하나 배치할 수 있다. 방문 횟수보다 원래 정점이 더 많다면, 남은 정점 하나마다 비용 $1$이 추가된다.

다음을 정의하자.

$$B=2(|V(H)|-1)+\sum_{v\in V(H)}\max(0,c_v-\deg(v)).$$

$P$의 내부 정점이 되면서 추가 비용이 $1$ 생기는 것은 $c_v\geq\deg(v)$인 정점뿐이다. 이러한 정점을 표시된 정점이라고 하자. 경로 $P$를 선택했을 때의 답은

$$B-\left(|E(P)|-\#\{P\text{의 표시된 내부 정점}\}\right)$$

이다. 따라서 괄호 안의 값을 최대로 만들면 된다.

트리를 임의의 정점에 루팅하자. $down_v$를 $v$를 한쪽 끝점으로 하고 $v$의 서브트리 안으로 내려가는 경로의 최대 괄호 값이라고 하자. 자식 $u$ 방향으로 내려가는 경로의 값은

$$1+\max(0,down_u-[u\text{가 표시됨}])$$

이다. 각 정점에서 가장 큰 두 값을 관리하면, $v$를 끝점으로 하는 경로와 $v$를 내부 정점으로 하는 경로를 모두 확인할 수 있다. 재귀 깊이 문제를 피하기 위해 정점 순서를 먼저 만든 뒤 역순으로 계산한다.

$H$가 정점 하나뿐이라면 모든 원래 정점 사이의 거리가 $1$이므로 답은 $N-1$이다.

DSU와 트리 DP를 사용한다. 시간 복잡도는 $O(N\alpha(N))$, 공간 복잡도는 $O(N)$이다.

서브태스크 1에서는 트리의 지름을 $D$라 할 때 답이 $2(N-1)-D$이다. 서브태스크 2에서는 압축한 트리의 각 정점을 시작점으로 삼아 모든 경로의 이득을 직접 계산하는 $O(N^2)$ 풀이를 사용할 수 있다.