풀이

1967번 문제의 하드 버전으로 문제는 동일하다.

입력 범위가 10004에서 100000으로 10배 늘어 기존 알고리즘으로는 풀지 못한다.

트리의 지름 문제는 정석 풀이법이 알려져 있는 WELL-KNOWN 문제라고 한다.

위 문제의 풀이가 WELL-KNOWN 풀이법에 상당히 근접했는데 아쉽다.

이전에는 루트 노드에서 리프 노드들을 찾아준 후, 각 리프에서 탐색을 진행했다.

처음에 루트 노드에서 가장 먼 정점을 찾아주고, 그 정점에서 다시 가장 먼 정점을 찾아주면 DFS를 2번만 사용해서 O(N)에 풀 수 있다.

상당히 정석 풀이법에 근접했는데 아쉬울 따름이다.