접근성 (Accessibility)

문제

인덱스국 도로교통 : Day 3

인덱스국은 N개의 도시와 M개의 도로들로 이루어져 있었으나, 최근 국왕 (검열됨)이 유지비가 많이 나간다는 이유로 도로를 N − 1개로 줄여버렸습니다. 다행히도 도로들을 이용하면 임의의 두 도시 사이를 이동할 수 있다고 합니다. 국왕 (검열됨)의 오른팔 앤디는 도로들이 줄어든 탓에 국민들의 청원이 계속되어 과로사할 지경에 이르렀습니다. 너무 일을 많이 해서 이상해진 앤디는 사람들을 접근성이 높은 도시로 강제 이사를 시키면 청원이 줄어들 것이라고 생각하고, 일단 모든 도시들의 접근성을 계산하기로 결정했습니다. dist(x, y)는 도시 x와 도시 y 사이를 이동하기 위해 걸어야 하는 최단 거리로 정의됩니다. 도시 x의 접근성 access(x)는 $\sum_{i=1}^{N} \text{dist}(\text{x}, i)$로 정의됩니다. 앤디가 과로사하지 않도록 모든 도시들의 접근성을 계산하는 프로그램을 만들어주도록 합시다.

구현 세부 사항

다음 함수를 구현하세요.

int64[] getAccessibility(int S[], int E[], int L[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.

• S, E, L은 크기 N − 1의 배열으로, 모든 0 ≤ i ≤ N − 2에 대해 도시 S[i]와 도시 E[i]를 연결하는 거리 L[i]의 도로가 존재합니다.

• 이 함수는 R[i] = access(i + 1)이 되는 크기 N의 배열 R을 반환해야 합니다.

제한 조건

• 1 ≤ N ≤ 300,000
• 1 ≤ S[i], E[i] ≤ N (0 ≤ i ≤ N − 2)
• 1 ≤ L[i] ≤ $10^8$ (0 ≤ i ≤ N − 2)
• 도로들을 이용하여 임의의 두 도시 사이를 이동할 수 있습니다.

서브태스크

서브태스크	점수	N
1	2	N ≤ 1,000
2	8	N ≤ 300,000

예제 입출력

N = 4, S = [1, 1, 1], E = [2, 3, 4], L = [1, 2, 3]

그레이더는 다음 함수를 호출합니다.

getAccessibility([1, 1, 1], [2, 3, 4], [1, 2, 3]) = [6, 8, 10, 12]

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

• line 1 : N
• line 2 + i (0 ≤ i ≤ N − 2) : S[i] E[i] L[i]