왕국의 가장 먼 두 도시
골드 V의견: 0
마법 왕국에는 \(N\)개의 도시가 있고, \(N-1\)개의 마법 도로로 연결되어 있어 어떤 두 도시 사이에도 정확히 하나의 경로가 존재한다. 각 도로에는 양의 정수 가중치(이동 비용)가 붙어 있다.
탐험가 리아는 두 도시를 골라 그 사이의 경로를 걷는 여행을 계획하고 있다. 리아는 최대한 많은 비용이 드는 경로를 걷고 싶다. 가능한 모든 두 도시 쌍 \((u, v)\) 중에서 경로의 가중치 합이 최대인 값을 구하여라.
\((u, u)\)처럼 같은 도시에서 시작하고 끝나는 경우의 합은 \(0\)이다.
- \(1 \le N \le 200\,000\)
- \(0 \le w \le 10^9\)
- 주어진 그래프는 트리임이 보장된다.
첫째 줄에 도시의 수 \(N\)과 도로의 수 \(N-1\)이 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 도로의 양 끝점 \(u\), \(v\)와 가중치 \(w\)가 공백으로 구분되어 주어진다. 도로는 양방향이다.
가중치 합이 최대인 경로의 가중치 합을 출력한다.
1 0
0
노드가 하나뿐이므로 경로 길이는 \(0\)이다.
4 3
1 2 3
2 3 1
3 4 4
8
경로 \(1\to2\to3\to4\)의 가중치 합은 \(3+1+4=8\)로 가장 크다.
5 4
1 2 10
1 3 7
1 4 2
1 5 5
17
별 모양 트리에서 가장 먼 경로는 도시 \(2\)에서 도시 \(3\)을 잇는 경로로, 가중치 합 \(10+7=17\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
왕국의 가장 먼 두 도시
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
왕국의 가장 먼 두 도시