R01327
탐험로 지름
실버 I레이팅
의견: 0
설명
탐험가 지우는 \(N\)개의 캠프가 트리 형태로 연결된 탐험로를 지도화하고 있다. 각 길에는 이동 거리(양의 정수)가 표시되어 있다.
트리의 지름은 두 캠프를 연결하는 경로 중 길이가 가장 긴 경로의 길이이다.
탐험로의 지름을 구하여라.
제약
- \(1 \le N \le 100\,000\)
- \(1 \le w \le 1\,000\)
- 주어진 그래프는 항상 트리이다 (연결된 무방향 그래프, 사이클 없음).
입력 형식
첫째 줄에 캠프의 수 \(N\)과 길의 수 \(N-1\)이 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 길이 연결하는 두 캠프 번호 \(u\), \(v\)와 그 길의 거리 \(w\)가 공백으로 구분되어 주어진다.
출력 형식
탐험로의 지름을 출력한다.
예제 1
입력
5 4
1 2 3
2 3 2
3 4 5
2 5 1
출력
10
설명
노드 \(1\)에서 \(4\)까지의 경로 \(1 \to 2 \to 3 \to 4\)의 길이는 \(3+2+5=10\)이다. 이것이 가장 긴 경로이므로 지름은 \(10\)이다.
예제 2
입력
4 3
1 2 7
1 3 4
1 4 9
출력
16
설명
별 모양 트리에서 노드 \(2\)와 \(4\) 사이의 거리가 \(7+9=16\)으로 가장 길다. 지름은 \(16\)이다.
힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
탐험로 지름
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
탐험로 지름
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기