d(i, j) : i번째 도시까지 가는데 j개의 도로를 포장했을 때 이르는 최단거리.

O(E log E) 다익스트라 돌 듯이 해주면 됩니다.

트리 분할 문제는 트리 말단 노드에서부터 올라오면서 d(i, j) : i번 노드를 포함하는 부트리에서 j개의 정점을 선택할 때 생기는 간선 가중치의 합의 최솟값이라고 접근하면 됬던 것 같습니다. 답은 d(루트 노드, K)가 되겠군요. 대회 당시에는 만점자가 없었던(?) 걸로 기억하는데 옛날 ko4u 사이트에 이후연(ltdtl)님이 깔끔한 정해를 써주셨는데 지금은 사이트가 폭파되어서 사라졌네요...

오호라... 그렇군요 감사합니다 ㅎㅎ 그런데 도로포장 문제에서 K번 다익스트라를 돌아주는 방식인 건가요? 진짜 그래프는 잘 모르겠어서... 도로포장 조금만 더 자세히 설명해주시면 안 될까요?

보통 저는 우선순위큐로 새로 봐야할 정점이 없을 때까지 돌리는데.. 음..

큐의 원소로 x(a, b) = (정점, 포장한 도로 개수)라고 두면 됩니다.

while (Q에 원소가 있을 동안) {

1) 연결된 간선들 보면서 그냥 건너갈 때

2) 포장한 도로 개수가 K보다 작아서 새로 포장할 수 있을 때

}

이렇게 짜면 됩니당.