트리 쪼개기

정점 $v$의 차수를 $\deg(v)$라고 하자.

$\deg(v) \geq 2$라면 답은 $0$이다. $v$ 하나를 제거하면 $v$에 연결되어 있던 각 방향이 서로 다른 연결 컴포넌트가 되므로, 정확히 $\deg(v)$개의 연결 컴포넌트가 남는다.

이제 $v$가 리프라고 하자. $v$에서 가장 가까운 차수가 $3$ 이상인 정점을 $b$라고 하고, $v$와 $b$ 사이의 거리를 $d$라고 하자.

$k<d$일 때 제거되는 정점들은 $v$에서 시작하는 하나의 단순 경로를 이룬다. 이 경로의 끝에 도달하기 전까지 차수가 $3$ 이상인 정점이 없으므로, 남은 그래프는 연결되어 있거나 비어 있다. 따라서 연결 컴포넌트가 $2$개 이상이 될 수 없다.

$k=d$이면 $b$도 제거된다. $b$에서 $v$ 방향으로 향하는 간선을 제외해도 $b$에는 적어도 두 개의 다른 방향이 있다. 이 방향들은 $b$를 제거한 뒤 서로 다른 연결 컴포넌트가 된다. 따라서 리프 $v$의 답은 $d$이다.

차수가 $3$ 이상인 정점이 트리에 하나도 없다면 트리는 하나의 경로이다. 경로의 리프를 중심으로 어떤 반지름의 정점들을 제거해도 남은 그래프는 하나의 경로이거나 빈 그래프이므로 답은 $-1$이다. $N=1$인 경우도 같은 이유로 답은 $-1$이다.

따라서 다음과 같이 답을 정리할 수 있다.

• 차수가 $2$ 이상인 정점의 답은 $0$이다.
• 리프의 답은 가장 가까운 차수가 $3$ 이상인 정점까지의 거리이다. 그러한 정점이 없으면 $-1$이다.
• 차수가 $0$인 정점의 답은 $-1$이다.

차수가 $3$ 이상인 모든 정점을 시작점으로 하는 다중 시작점 BFS를 수행하면, 각 정점에서 가장 가까운 이러한 정점까지의 거리를 한 번에 구할 수 있다.

시간 복잡도는 $O(N)$이고, 메모리 복잡도는 $O(N)$이다.