Доброго времени суток!

Пытаюсь решить "Камелот". В тэгах стоит декартово дерево. На данный момент у меня есть дерево, где каждая вершина i — крепость. с(i) — количество рыцарей и охранников в i-й крепости. w(i, j) — минимальная стоимость пути из крепости i в j. И нужно найти такую вершину i, что сумма всех с(j) * w(j, i) для всех j минимальна. Проблема в быстром нахождении места встречи и у каких K крепостей нужно обнулить стоимость дани. Как это сделать? Большое спасибо.