[BOJ] 1967

트리의 지름

1967번 https://www.acmicpc.net/problem/1967

트리(tree)는 사이클이 없는 무방향 그래프이다.
트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다.
트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다.
이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

1967번 문제에 그대로 들어가있는 문장인데, 여태 트리의 지름을 구할 때
임의의 노드로부터 가장 먼 노드 u를 구한 다음,
u로부터 가장 먼 노드 v를 구하면, u와 v사이의 거리가 트리의 지름이다.
라는걸 공식처럼 사용하곤 했는데, 위의 그림을 보고 완전히 이해가 됐습니다.

가장 먼 두 노드를 양끝으로 쭉 늘린 것이기 때문에 어떤 점도 저 원을 벗어날 수 없게 됩니다.
저 원 위에는 다른 노드가 존재할 수도 있는데, 원이기 때문에 그런 경우에도 문제 없이 일관된 방식으로 지름을 구할 수 있습니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1967.cpp