6190 : 트리 지름 쿼리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
처음에 N개의 독립된 노드가 존재하고, 단계별로 간선이 추가되어 합쳐집니다. 간선이 추가될 때마다 현재 합쳐진 컴포넌트의 최대 지름(가장 먼 노드 쌍의 거리)을 출력하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N-1개의 줄에 추가되는 간선 정보 u, v가 주어집니다. 추가된 간선에 의해 사이클이 발생하지 않음이 보장됩니다.
둘째 줄부터 N-1개의 줄에 추가되는 간선 정보 u, v가 주어집니다. 추가된 간선에 의해 사이클이 발생하지 않음이 보장됩니다.
출력 설명
간선이 하나씩 추가될 때마다 현재 합쳐진 트리의 지름을 한 줄씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2
1 3
2 4
2 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
2
3
3