Гонцы Шёлкового пути
В Средние века через Ош проходил Великий шёлковый путь. Дороги от караван-сараев сходились к Ошу так, что из любого из 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 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии