트리의 지름

면접 대비

시간 제한2초메모리 제한256 MB

요약
정점이 최대 10만 개인 가중치 트리에서 두 정점 사이의 최대 거리인 지름을 구하는 문제입니다.
난이도

보통10점 중 5점

유형
트리, DFS, BFS, 그래프
정답자
아직 제출이 없습니다

문제

트리에서 두 정점 사이의 거리는 두 정점을 잇는 유일한 경로에 포함된 간선 가중치의 합입니다. 트리의 지름은 가능한 모든 두 정점 사이 거리 중 최댓값입니다. 주어진 가중치 있는 트리의 지름을 구하세요.

입력

첫째 줄에 정점의 개수 V (2 <= V <= 100000)가 주어집니다. 정점 번호는 1부터 V까지입니다.

이어서 V개의 줄에 각 정점과 인접한 간선 정보가 주어집니다. 각 줄은 정점 번호로 시작하고, 그 뒤에 인접 정점 번호 거리 쌍이 0개 이상 이어집니다. 각 줄의 마지막에는 -1이 주어집니다. 모든 거리는 10000 이하의 자연수입니다.

출력

트리의 지름을 출력합니다.

예제1

  1. 예제 1

    입력
    5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1
    예상 출력
    11