알파카 산책로의 기복
플래티넘 V의견: 0
알파카 목장 \(n\)곳이 \(n-1\)개의 산책로로 트리 형태로 연결되어 있다. 각 산책로에는 험준도 \(w\)가 있다.
알파카가 목장 \(a\)에서 목장 \(b\)까지 산책하면, 그 산책의 기복은 (경로에서 가장 험준한 길의 험준도) \(-\) (가장 평탄한 길의 험준도)이다. 길 하나만 지나는 산책의 기복은 \(0\)이다.
서로 다른 모든 목장 쌍 \(\{a, b\}\)에 대해 산책했을 때 기복의 총합을 구하여라. \((a, b)\)와 \((b, a)\)는 같은 산책으로 친다.
\(1 \le n \le 100\,000\), \(1 \le w \le 10^9\). 답은 64비트 정수 범위 안에 들어간다.
첫째 줄에 목장의 수 \(n\)이 주어진다. 다음 \(n-1\)개의 줄에 산책로의 정보 \(x\ y\ w\)가 주어진다 — 목장 \(x\)와 \(y\)를 잇는 험준도 \(w\)의 길이다.
모든 목장 쌍에 대한 기복의 총합을 출력한다.
4
1 2 3
2 3 1
3 4 5
10
간선 하나짜리 경로는 기복이 \(0\)이다. \((1,3)\)은 \(3-1=2\), \((1,4)\)는 \(5-1=4\), \((2,4)\)는 \(5-1=4\) — 합은 \(10\)이다.
4
1 2 7
1 3 7
1 4 7
0
모든 길의 험준도가 같으면 어떤 산책도 기복이 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
알파카 산책로의 기복
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
알파카 산책로의 기복