Как мы знаем, Элой и Варл отправились на поиски резервной GAIA. Одно из мест, где могла бы она находиться — заброшенная подземная лаборатория компании «Далекий Зенит».
Лаборатория состоит из $$$n$$$ комнат, расположенных в горе. Комната с номером $$$i$$$ находится на глубине $$$d_i \geqslant 0$$$ метров от уровня земли. Если $$$d_i = 0$$$, то комната находится на поверхности.
Поскольку лаборатория долгое время не использовалась, комнаты успели замерзнуть и обледенеть, и теперь в комнате номер $$$i$$$ расположено $$$a_i$$$ единиц льда. Чтобы избавляться от льда и талой воды, между комнатами была построена сеть из $$$n$$$ труб. Для каждого $$$i$$$ из комнаты номер $$$i$$$ выходит ровно одна труба вниз; эта труба ведет в комнату номер $$$b_i$$$, расположенную на большей глубине. На самой большой глубине расположена единственная комната; труба из нее ведет в подземное озеро.
Пропускная способность каждого метра трубы равна единице воды в минуту. Это означает, что если в комнате есть вода, за оду минуту по трубе из нее вытекает ровно одна единица воды. Кроме того, если в момент времени $$$t$$$ минут единица воды начала течь по трубе длины $$$d_{b_i} - d_i$$$ из комнаты $$$i$$$ в комнату $$$b_i$$$, то эта единица попадет в комнату $$$b_i$$$ в момент времени $$$t + d_{b_i} - d_i$$$ минут.
Изначально вода во всех комнатах лаборатории находилась в замерзшем состоянии. Из-за нарушения биосферы в момент времени $$$0$$$ минут лед в комнатах на поверхности мгновенно растаял и начал течь по трубам вниз.
Когда растаявшая вода впервые доходит до низа трубы, ведущей в вершину $$$i$$$, весь лед в этой комнате мгновенно тает, и вода начинает течь по трубе $$$i \to b_i$$$ со скоростью $$$1$$$ метр в минуту. Обратите внимание, что лед тает моментально, и вода не задерживается в комнате. Другими словами, если к моменту времени $$$t$$$ минут в комнату $$$i$$$ попала первая единица воды, к тому же моменту времени вода заполнит трубу $$$i \to b_i$$$ на одну единицу. Комнаты можно считать неограниченными по объему, то есть вмещающими произвольное количество единиц воды.
Элой подозревает, что оборудование, которое долго находилось в комнатах с большим уровнем воды, могло испортится. Поэтому она хочет узнать, сколько минут в комнате $$$r_i$$$ талая вода была на уровне не меньше $$$x_i$$$ (в комнате находилось хотя бы $$$x_i$$$ единиц воды). Помогите героине узнать ответы на $$$m$$$ запросов такого вида.
В первой строке через пробел даны два целых числа $$$n$$$ и $$$m$$$ — количество комнат в лаборатории и количество запросов ($$$1 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant m \leqslant 2 \cdot 10^5$$$).
В следующих $$$n$$$ строках дается описание комнат: в $$$i$$$-й через пробел перечислены три целых числа $$$b_i$$$, $$$d_i$$$ и $$$a_i$$$ — номер комнаты, в которую ведет труба из комнаты $$$i$$$, глубина комнаты, и количество замерзшей воды в ней ($$$0 \leqslant b_i \leqslant n$$$; $$$0 \leqslant d_i, a_i \leqslant 10^6$$$).
Равенство $$$b_i = 0$$$ означает, что вода из этой комнаты стекает в подземное озеро неограниченного объема. Гарантируется, что существует единственное $$$i$$$, для которого $$$b_i = 0$$$.
Равенство $$$d_i = 0$$$ означает, что комната номер $$$i$$$ находится на поверхности. Гарантируется, что если $$$b_i > 0$$$, то $$$d_i < d_{b_i}$$$.
В $$$i$$$-й из $$$m$$$ следующих строк через пробел даны два целых числа $$$r_i$$$ и $$$x_i$$$ — номер комнаты и интересущий уровень воды в ней в рамках $$$i$$$-го запроса ($$$1 \leqslant r_i \leqslant n$$$; $$$1 \leqslant x_i \leqslant 10^9$$$).
В $$$m$$$ строках выведите по одному целому числу — время (в минутах), в течение которого в комнате $$$r_i$$$ уровень воды был не меньше $$$x_i$$$.
Отвечая на запросы, следует учитывать только то время, когда вода находилась в жидком состоянии.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 16 | $$$n, m \leqslant 100$$$, $$$d_i, a_i \leqslant 100$$$ для всех $$$i$$$ | – | полная |
2 | 14 | все $$$b_i$$$ различны (в каждую подземную комнату ведет ровно одна труба сверху) | – | полная |
3 | 16 | в каждую подземную комнату ведут ровно две трубы сверху; все $$$d_{b_i} - d_i$$$ равны (все трубы имеют одинаковую длину) | – | полная |
4 | 12 | $$$n, m \leqslant 100$$$ | 1 | полная |
5 | 18 | $$$n, m \leqslant 2000$$$ | 4 | первая ошибка |
6 | 24 | нет | 1 – 5 | первая ошибка |
3 6 3 0 2 3 0 3 0 2 1 1 2 2 4 2 1 3 1 3 2 3 3
0 0 2 5 3 1
5 10 5 0 2 4 0 3 4 0 1 5 1 2 0 3 1 4 1 4 2 4 3 4 4 4 5 5 1 5 2 5 3 5 4 5 5
5 4 2 0 0 8 6 4 0 0
Рассмотрим первый тест:
Таким образом, ответы на запросы будут такими:
Ниже приведено изменение заполненности комнат для второго примера в первые 10 минут, начиная с 0.