문제 태그 : https://www.acmicpc.net/problem/15647 문제 소개 간선의 가중치가 있는 트리가 주어진다. 1번 노드 부터 N번 노드까지 각 노드에 대해서 다른 모든 노드에서 그 노드까지의 거리의 합을 출력하시오. 문제 풀이 처음에는 하나당 O(logN)에 구하는 방법을 생각했다. HLD나 centriod decomposition을 떠올렸지만, 잘 모르는 쪽이기 때문에 더 이상 풀이를 떠올릴 수 없었다. 분명히 centriod를 활용해 풀 수 있을 것 같긴하다. 그래서 전체를 O(N)으로 구하는 방식으로 바꾸었다. Tree DP를 이용하는 방식이다. F[i] = 내 서브트리의 노드들이 i번 노드까지 오는데 걸리는 거리의 합 cnt[i] = 내 버스트리의 노드 수 dp[i] = 내..