•시간제한: 2.000 S •메모리제한: 256 MB •제출: 0 •통과: 0 •만든사람: suakii

6175 : 트리에서 DP 최적화

시간 2.000s · 메모리 256MB · 제출 0 · 정답 0

채점기록 통계 묻고답하기

트리를 적절히 K개의 서브트리로 분할할 때 발생하는 각 서브트리의 (노드 수)^2의 합을 최소화하는 비용을 구하시오.

첫째 줄에 노드의 개수 N (1 ≤ N ≤ 5,000)과 분할할 서브트리의 수 K (1 ≤ K ≤ min(N, 10))가 공백으로 구분되어 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다.

분할할 때 발생하는 최소 비용을 출력합니다.