Don't Mess with the Moles

지점 $w$의 두더지가 거리만으로 지점 $u$를 유일하게 알아낼 때, $w$가 $u$를 식별한다고 하자. 트리가 경로라면 끝점 하나에서 모든 거리가 다르므로 두더지 한 마리면 충분하다. 이하에서는 경로가 아닌 트리를 생각한다.

리프의 집합을 $F$, 어떤 리프에서도 식별되지 않는 지점의 집합을 $B$라 하면 $F\cup B$에 배치하는 것이 최적이다.

이제 $B$를 구하자. 간선 $xy$를 끊은 뒤 $x$ 쪽 성분을 $C_{x\to y}$라 하고, 그 높이와 지름을

$$h_{x\to y}=\max_{v\in C_{x\to y}} d(x,v),\qquad D_{x\to y}=\operatorname{diam}(C_{x\to y})$$

로 둔다. 비리프 $u$가 어떤 리프에서 식별될 필요충분조건은, 어떤 이웃 $a$에 대해 $h_{a\to u}=D_{a\to u}$인 것이다.

이 방향별 값은 리루팅 DP로 계산한다. $x\to y$를 구할 때 $z\neq y$인 이웃들의 가지 높이 $1+h_{z\to x}$와 두 개의 중 큰 두 값을 라 하면

$$h_{x\to y}=t_1,\qquad D_{x\to y}=\max\left(t_1+t_2,\max_{z\neq y}D_{z\to x},0\right).$$

자식에서 부모, 부모에서 자식 순으로 계산하되, 가지 높이 상위 $3$개와 지름 상위 $2$개를 보관하면 이웃 하나를 제외한 값도 상수 시간에 구한다. 모든 리프와 위 조건을 만족하는 이웃이 없는 비리프에 배치한다. 시간과 공간 복잡도는 $O(N)$이다.

증명

$w\neq u$가 $u$를 식별한다고 하자. $u$에서 $w$ 방향의 이웃을 $a$, 간선 를 끊었을 때 쪽 성분을 라 하면