Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Планета Терминус, на которой размещается Первое Основание, бедна ресурсами. Всю энергию жители получают от
ядерных реакторов, которым требуется урановое топливо. Немногочисленные месторождения урана залегают глубоко под землей, поэтому
для его добычи построена разветвленная сеть из `N` горных выработок, связанных между собой соединительными тоннелями.
Выработка номер 1 имеет выход на поверхность, все остальные расположены в глубине. Прокладка соединительных тоннелей -- тяжелое и затратное дело,
поэтому проложить удалось только минимально необходимое их количество. Из-за этого существует ровно один путь от каждой из
выработок до выхода на поверхность.
Когда роботы-шахтеры добывают в одной из выработок очередную партию урана, её нужно доставить на поверхность.
Подъем партии по тоннелю требует определенного количества энергии (не зависящего от размера партии).
Стоимость подъема может меняться: увеличиваться (например, если в тоннеле произошел обвал и передвижение по нему затруднено)
или уменьшаться (например, если в тоннеле построили эффективный подъемник). Из-за этого некоторые партии становится выгоднее
поднимать на поверхность не сразу после добычи, а дождавшись более подходящего момента в будущем, но в обоих случаях поднимать
партию урана нужно сразу до поверхности, а до не какой-то промежуточной точки.
Некоторые партии имеет смысл и вовсе бросить и не доставлять на поверхность, если затраты на их подъем не окупятся в любом случае.
Ваша задача -- по информации о добываемых партиях урана и стоимостях подъема определить, сколько энергии получит Терминус при оптимальном
планировании добычи.
В первой строке ввода содержится два целых числа: количество выработок `N` (`1<=N<=10^5`) и количество событий `Q` (`1<=Q<=10^5`).
Затем следует `N-1` строка -- описания тоннелей. Каждое описание включает три целых числа: номера пары выработок,
соединенных тоннелем (от 1 до `N`), и стоимость подъема в начальный момент времени (от 0 до `10^5`, в энергетических единицах).
Затем следует `Q` строк -- описания событий в том порядке, в котором они происходили, первое число в каждой строке -- тип события.
* Тип 1 -- добыта партия урана, затем следует два целых числа: номер выработки, в которой добыта партия (от 1 до `N`) и количество добытого урана (в энергетических единицах, от 1 до `10^5`).
* Тип 2 -- изменилась стоимость подъема по тоннелю, затем следует два целых числа: номер тоннеля (от 1 до `N-1`, соответствует номеру строки описания), и изменение стоимости (от `-10^5` до `10^5`; гарантируется, что стоимость в любой момент неотрицательна).
Выведите единственное неотрицательное целое число -- максимально возможное количество добытой
энергии (общее количество поднятого на поверхность урана за вычетом затрат на его подъем). Любую из партий разрешается
поднимать в любой момент времени (в том числе, после последнего события), но не раньше момента её добычи.
Любые партии разрешается бросать в выработке (в этом случае партия не приносит энергии, но и не требует затрат на подъем).
```sample Пример ввода
4 5
1 2 10
2 3 50
2 4 15
1 4 200
1 3 50
2 2 -45
2 1 35
1 4 50
```
```sample Пример вывода
210
```
*Пояснение к примеру*
* Первую партию стоит доставить на поверхность сразу же после добычи, затраты на подъем составят 15 (от выработки 4 до 2) + 10 (от выработки 2 до 1).
* Вторую партию стоит доставить на поверхность в промежутке между событиями 3 и 4 (когда стоимость подъема по тоннелю 2 уже уменьшилась, а по тоннелю 1 -- еще не увеличилась). В этом случае затраты на подъем составят 5 (от выработки 3 до 2) + 10 (от выработки 2 до 1).
* Третью партию стоит бросить, так как затраты на подъем из выработки 4 к этому моменту составляют 60 и превышают выгоду от доставки её на поверхность.
Итоговое количество равно: (200-15-10) + (50-5-10) = 175 + 35 = 210 энергетических единиц.
Начало
Рабочее место участника
Задачи на деревьях