모든 도시까지의 거리 합
골드 III의견: 0
왕국에는 \(N\)개의 도시가 있고, \(N-1\)개의 도로로 연결된 트리를 이룬다. 모든 도로의 길이는 \(1\)이다.
각 도시 \(v\)에 대해, \(v\)에서 나머지 모든 도시까지의 거리 합 \(S(v) = \sum_{u=1}^{N} d(v, u)\)를 구하여라.
여기서 \(d(v, u)\)는 도시 \(v\)와 도시 \(u\) 사이의 도로 수이다.
- \(1 \le N \le 200\,000\)
- 주어진 그래프는 트리임이 보장된다.
첫째 줄에 도시의 수 \(N\)이 주어진다.
다음 \(N-1\)개의 줄에 도로의 양 끝점 \(u\), \(v\)가 공백으로 구분되어 주어진다. 도로는 양방향이다.
도시 \(1, 2, \dots, N\)의 순서대로 \(S(v)\) 값을 한 줄에 공백으로 구분하여 출력한다.
1
0
노드가 하나뿐이므로 거리 합은 \(0\)이다.
3
1 2
2 3
3 2 3
경로 트리 \(1-2-3\)에서:
- 도시 \(1\): \(d(1,2)+d(1,3) = 1+2 = 3\)
- 도시 \(2\): \(d(2,1)+d(2,3) = 1+1 = 2\)
- 도시 \(3\): \(d(3,1)+d(3,2) = 2+1 = 3\)
4
1 2
1 3
1 4
3 5 5 5
별 모양 트리에서:
- 도시 \(1\) (중심): 잎까지 거리 \(1\)씩 세 개, 합 \(3\)
- 도시 \(2, 3, 4\) (잎): 중심까지 \(1\), 나머지 잎까지 \(2\)씩 두 개, 합 \(5\)
riseoj 작성
출처 Original
평가 및 의견
모든 도시까지의 거리 합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
모든 도시까지의 거리 합