Это сложная версия задачи. В трех версиях отличаются ограничения на \(n\) и \(m\). Вы можете совершать взломы только в том случае, если решены все версии задачи.
Пак Чанек устанавливает интернет-связь в деревне Кхунтиен. Деревню можно представить как связный простой граф с \(n\) домами и \(m\) интернет-кабелями, соединяющими дом \(u_i\) и дом \(v_i\), каждый с задержкой \(w_i\).
Существует \(p\) домов, которым требуется интернет. Пак Чанек может установить серверы не более чем в \(k\) домов. Дома, которым нужен интернет, будут подключены к одному из серверов. Однако, поскольку каждый кабель имеет свою задержку, задержка, которую испытывает дом \(s_i\), нуждающийся в интернете, будет равна максимальной задержке кабелей между этим домом и сервером, к которому он подключен.
Для каждого \(k = 1,2,\ldots,n\), помогите Пак Чанеку определить минимальную суммарную задержку, которая может быть достигнута для всех домов, требующих интернет.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел: минимальное общее время ожидания, которое может быть достигнуто для всех домов, нуждающихся в интернете для каждого \(k = 1,2,\ldots,n\).
Примечание
В первом наборе входных данных для \(k=3\) одним из лучших решений является установка серверов в вершинах \(2\), \(6\) и \(8\) и получение следующей задержки:
- задержка\((2) = 0\)
- задержка\((5) = \max(3, 5) = 5\)
- задержка\((6) = 0\)
- задержка\((8) = 0\)
- задержка\((9) = \max(2, 4) = 4\)
Таким образом, общая задержка составит \(9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
9 8 5
2 5 6 8 9
1 2 1
1 3 2
3 4 10
4 5 3
4 6 5
1 7 10
7 8 4
7 9 2
3 3 2
3 1
1 2 1
2 3 3
1 3 2
|
34 19 9 4 0 0 0 0 0
2 0 0
|