시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 128 MB | 334 | 186 | 152 | 55.678% |
로스팅하는 엠마는 바리스타입니다. 엠마는 N개의 정점을 가진 트리 형태의 농장 연결 시스템을 구축한 상태입니다. 트리의 정점은 1번부터 N번까지 번호가 매겨져 있습니다. 각각의 간선은 그 농장에서 다른 농장으로 이동할 수 있음을 뜻하며, 간선의 가중치는 이동 거리를 뜻합니다.
엠마는 한 개의 농장을 정해 농장 옆에 로스팅 시설을 마련하려고 합니다. 이때, 다른 농장에서 로스팅 시설까지의 거리의 합들을 알아야, 효율적으로 로스팅 시설의 위치를 정할 수 있을 것입니다. 그러므로 각각의 농장마다 다른 농장들에서 그 농장으로 가는 최단 거리들의 합을 구해줍시다.
첫째 줄에 N이 입력됩니다. (1 ≤ N ≤ 3 × 105)
N-1 줄 동안 세 수 u, v 와 d가 주어집니다. 이는 u번째 농장과 v번째 농장은 서로 연결되어 있으며, 그 거리는 d임을 뜻합니다. (1 ≤ u, v ≤ N, 1 ≤ d ≤ 5)
주어지는 그래프는 트리입니다.
N개의 줄 동안 각각의 농장에 대해 다른 농장들에서 그 농장으로 가는 최단 거리들의 합을 출력합니다.
10 1 2 1 2 3 1 2 4 1 4 7 1 4 8 1 4 5 1 1 6 1 6 9 1 6 10 1
19 17 25 19 27 23 27 27 31 31