6163 : 트리 종합 1
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
방향성이 있는 트리 간선 정보와 가중치가 주어집니다. 이 트리에서 유일한 루트를 찾고, 해당 트리의 가장 먼 두 노드 사이의 경로(지름)의 양 끝점 및 지름 길이를 구하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N-1개의 줄에 부모에서 자식으로 향하는 간선 정보 u, v와 그 가중치 w가 공백으로 구분되어 주어집니다.
둘째 줄부터 N-1개의 줄에 부모에서 자식으로 향하는 간선 정보 u, v와 그 가중치 w가 공백으로 구분되어 주어집니다.
출력 설명
루트 노드의 번호, 지름의 시작점 노드 번호, 끝점 노드 번호(시작점 < 끝점), 그리고 지름 길이를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2 3
1 3 4
3 4 2
3 5 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 5 13