8054 : 트리의 지름
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 노드로 구성된 트리가 주어집니다. 트리에서 두 노드 사이의 거리(간선의 개수) 중 최댓값(즉, 트리의 지름)을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 200{,}000$
• $1 \le a, b \le N$
[제약 조건]
• $1 \le N \le 200{,}000$
• $1 \le a, b \le N$
입력 설명
첫째 줄에 노드의 수 $N$이 주어집니다. ($1 \le N \le 200{,}000$)
다음 $N-1$개의 줄에 걸쳐 트리의 간선을 나타내는 두 노드 $a, b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$)
다음 $N-1$개의 줄에 걸쳐 트리의 간선을 나타내는 두 노드 $a, b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$)
출력 설명
트리의 지름을 나타내는 정수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2
1 3
2 4
3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
임의의 노드(예: $1$번 노드)에서 시작하여 가장 먼 노드 $u$를 찾은 뒤, 다시 $u$번 노드에서 시작하여 가장 먼 노드 $v$를 찾는 두 번의 BFS/DFS 탐색을 통해 지름을 $O(N)$에 구할 수 있습니다.