Ограничения: время – 500ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Система обороны планеты Кадия состоит из `N` крепостей. Крепости связаны минимально необходимым числом двусторонних подземных туннелей так, что от любой крепости можно добраться до любой другой по единственному маршруту. Планета находится под атакой культистов Хаоса. Для каждой крепости известно, сколько защитников в ней находилось в начале вторжения, и сколько культистов высаживается возле нее ежедневно (каждый день это число одно и то же). Каждый культист уничтожает 1 защитника, сам погибая при этом. Если в крепости не осталось защитников, то атаковавшие ее культисты (те, что выжили) мгновенно перемещаются по тоннелю в соседнюю крепость по направлению к столице и присоединяются к культистам, атакующим её. Если защитники и этой крепости будут побеждены - нападающие будут сразу же двигаться из неё все дальше к столице, пока в их отряде будет оставаться хотя бы 1 живой культист. Определите, через сколько дней столица Кадии падет, если силы защитников не пополняются и не перемещаются между крепостями. В некоторых из крепостей на момент падения столицы могут еще оставаться изолированные группы защитников - они обречены, и их можно не принимать во внимание.
В первой строке ввода содержится единственное натуральное число `N` (`1<=N<=10^5`) - количество крепостей.
Затем следуют `N` строк - описаний крепостей, по три числа в каждой:
- `p_i` - номер соседней крепости на пути к столице (крепости нумеруются от 1 до `N`, для столицы указано -1)
- `d_i` - количество защитников (целое, `0<=d_i<=10^5`)
- `a_i` - количество нападающих, которые прибывают к крепости каждый день (целое, `0<=a_i<=10^5`).
Гарантируется, что в столице присутствует как минимум 1 защитник.
Выведите единственное целое число - номер дня (считая, что вторжения началось в день 1), в который в столице не останется защитников. Если столица никогда не падет, выведите -1.
```sample Пример ввода
4
-1 10 1
1 100 5
1 0 1
3 5 3
```
```sample Пример вывода
3
```
Пояснение: в первый день культисты, штурмующие крепости с номерами 1 и 3, сразу атакуют столицу (в ней останется 8 защитников), а в крепости 4 останется 5-3=2 защитника. Во второй день 2 культиста из числа штурмующих крепость 4 погибнут в бою с оставшимися защитниками, а последний присоединится к штурму столицы. Теперь столицу штурмуют 3 культиста (по 1 из крепостей 1, 3 и 4), и защитников в ней остается 8-3=5. В третий день все культисты из крепостей 1, 3 и 4 (всего 1+1+3=5) штурмуют столицу и побеждают всех оставшихся защитников. В крепости 2 еще останется 85 защитников, но они не влияют на ответ.
Начало
Рабочее место участника
Задачи на деревьях