Гонцы Шёлкового пути


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В Средние века через Ош проходил Великий шёлковый путь. Дороги от караван-сараев сходились к Ошу так, что из любого из n городов в Ош вёл ровно один путь: города и дороги образуют дерево, Ош — город номер 1.

Срочные письма в Ош доставляли гонцы. В каждом городе i, кроме Оша, жил свой гонец: прежде чем выехать, ему нужно S[i] минут на сборы, а затем он скачет в сторону Оша, тратя V[i] минут на каждый километр. Город i соединён дорогой длиной L[i] километров со следующим городом на пути в Ош — городом p[i].

Письмо, отправленное из города i, сначала везёт гонец города i. В любом городе по пути гонец может передать письмо местному гонцу, который сначала собирается, а потом везёт письмо дальше по тем же правилам (и тоже может передать его в любом городе). В Оше письмо доставлено. Передача письма мгновенна.

Для каждого города i от 2 до n найдите наименьшее время доставки письма из i в Ош.

Рисунок

Входные данные

В первой строке — целое число n (1 ≤ n ≤ 200 000).

В каждой из следующих n − 1 строк — четыре целых числа p[i], L[i], S[i], V[i] для городов i = 2, 3, …, n по порядку (1 ≤ p[i] ≤ n, 1 ≤ L[i] ≤ 10⁴, 0 ≤ S[i] ≤ 10⁹, 1 ≤ V[i] ≤ 10⁶). Гарантируется, что из каждого города по дорогам i → p[i] можно добраться до Оша.

Выходные данные

Выведите в одной строке n − 1 чисел — наименьшее время доставки для городов 2, 3, …, n. Если n = 1, выведите пустую строку.

Пример 1

Вход:

5
1 10 5 2
2 3 4 10
2 6 20 1
4 5 0 7

Выход:

25 59 36 71

Пояснение

Из города 5 выгодно отдать письмо своему гонцу только до города 4 (0 + 7 · 5 = 35 минут), там его заберёт гонец города 4 и довезёт до Оша за 20 + 1 · 16 = 36 минут: всего 71 минута. Гонец города 3 едет медленно, поэтому в городе 2 письмо стоит передать местному гонцу: 4 + 10 · 3 + 25 = 59.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 15 n ≤ 3000
2 25 p[i] = i − 1 для всех i (все города стоят на одной дороге)
3 60 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.