R00407
모든 마을까지의 거리 합
플래티넘 III레이팅
의견: 0
설명
\(N\)개의 마을이 \(N-1\)개의 양방향 길로 연결되어 트리를 이룬다. 각 길에는 양의 정수 길이가 있다.
각 마을 \(v\)에 대해, \(v\)에서 다른 모든 마을까지의 거리(유일한 경로 위 길이의 합)를 전부 더한 값을 구하여라.
마을마다 탐색을 새로 하는 \(O(N^2)\) 풀이는 통과할 수 없다. 한 번의 계산 결과를 루트를 옮기며 재활용하는 트리 동적 계획법이 필요하다.
제약
\(1 \le N \le 200{,}000\)
\(1 \le w \le 1{,}000\)
\(1 \le a, b \le N\)
입력 형식
첫 줄에 마을의 수 \(N\)이 주어진다.
다음 \(N-1\)개의 줄에 길의 정보 \(a\), \(b\), \(w\)가 주어진다.
출력 형식
마을 \(1\)번부터 \(N\)번까지 순서대로, 각 마을의 거리 합을 한 줄에 하나씩 출력한다.
예제 1
입력
3
1 2 2
2 3 3
출력
7
5
8설명
마을 1: \(2 + 5 = 7\), 마을 2: \(2 + 3 = 5\), 마을 3: \(5 + 3 = 8\).
예제 2
입력
1
출력
0설명
마을이 하나뿐이므로 거리 합은 0이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
모든 마을까지의 거리 합
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
모든 마을까지의 거리 합
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기