두 번째 지름
플래티넘 V의견: 0
가중치가 있는 트리가 주어진다. 트리에서 서로 다른 두 정점 사이에는 유일한 경로가 있으므로, \(n\)개의 정점에서 \(\frac{n(n-1)}{2}\)개의 경로 길이를 얻을 수 있다.
이 길이들을 내림차순으로 정렬했을 때 두 번째 값을 구하여라. 즉, 가장 긴 경로 하나를 제외했을 때 남은 경로 중 가장 긴 길이이다. 같은 길이는 각각 따로 센다 — 가장 긴 길이를 갖는 경로가 두 개 이상이면 답은 지름과 같다.
\(3 \le n \le 200\,000\), \(1 \le w \le 10^9\). 답은 64비트 정수 범위 안에 들어간다.
첫째 줄에 정점의 개수 \(n\)이 주어진다. 다음 \(n-1\)개의 줄에 간선의 정보 \(u\ v\ w\)가 주어진다 — 정점 \(u\)와 \(v\)를 잇는 가중치 \(w\)의 간선이다.
두 번째로 긴 경로의 길이를 출력한다.
5
1 2 3
2 3 4
2 4 2
1 5 6
11
가장 긴 경로는 \(3\)–\(5\)의 \(13\), 두 번째로 긴 경로는 \(4\)–\(5\)의 \(2+3+6=11\)이다.
4
1 2 5
1 3 5
1 4 5
10
길이 \(10\)인 경로가 세 개(\(2\)–\(3\), \(2\)–\(4\), \(3\)–\(4\))나 있으므로 두 번째 값도 \(10\)이다.
골드 II
플래티넘 IV막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
두 번째 지름
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
두 번째 지름