Подземная лаборатория
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как мы знаем, Элой и Варл отправились на поиски резервной 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$$$.

Отвечая на запросы, следует учитывать только то время, когда вода находилась в жидком состоянии.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
116 $$$n, m \leqslant 100$$$, $$$d_i, a_i \leqslant 100$$$ для всех $$$i$$$ полная
214 все $$$b_i$$$ различны (в каждую подземную комнату ведет ровно одна труба сверху) полная
316 в каждую подземную комнату ведут ровно две трубы сверху; все $$$d_{b_i} - d_i$$$ равны (все трубы имеют одинаковую длину) полная
412$$$n, m \leqslant 100$$$1полная
518$$$n, m \leqslant 2000$$$4первая ошибка
624нет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

Примечание

Рассмотрим первый тест:

  1. В момент времени $$$0$$$ минут вода была в замерзшем состоянии. Сразу после этого лед в верхних комнатах начинает таять.
  2. Через минуту в первой и второй комнатах будут одна и две единицы воды соответственно. В трубах $$$1 \to 3$$$ и $$$2 \to 3$$$ находится по единице воды.
  3. Две минуты от начала в первой и второй комнатах будет ноль и одна единица воды, соответственно, а в трубах из них вниз — по две единицы воды.
  4. Поскольку трубы заполнены полностью, в следующий же момент лед в третьей комнате растает, и начнет стекать в озеро со скоростью $$$1$$$ ед./минуту, тогда как в комнату из двух труб будет втекать $$$2$$$ ед./минуту.
  5. К моменту времени $$$3$$$ минуты, таким образом, в третьей комнате будет две единицы воды, а комнаты $$$1$$$ и $$$2$$$ будут пусты. В трубе $$$1 \to 3$$$ будет оставаться еще одна единица воды в самом низу трубы, тогда как труба $$$2 \to 3$$$ будет полной.
  6. Еще через минуту в третьей комнате накопится три единицы воды, а труба $$$1 \to 3$$$ опустеет, из-за чего уровень воды в третьей комнате перестанет расти.
  7. В момент времени $$$5$$$ минут в третьей комнате все еще три единицы воды, но теперь в трубе $$$2 \to 3$$$ вода закончилась, значит за каждую следующую минуту количество воды в комнате $$$3$$$ будет уменьшаться на $$$1$$$.

Таким образом, ответы на запросы будут такими:

  1. В первой комнате две единицы воды находятся только в момент времени $$$0$$$, после чего это количество сразу начинает уменьшаться, поэтому ни на каком положительном отрезке времени уровень воды в первой комнате не достигает $$$2$$$.
  2. Во второй комнате уровень воды никогда не равен $$$4$$$.
  3. При этом уровень воды больше либо равен $$$1$$$ между моментами времени $$$0$$$ и $$$2$$$, то есть ровно $$$2$$$ минуты.
  4. В третьей комнате уровень воды становится равен $$$1$$$, как только лед тает (в момент времени $$$2$$$), и держится $$$\geqslant 1$$$ до момента времени $$$7$$$, после чего он упадет ниже.
  5. Аналогично, он не меньше $$$2$$$ между моментами времени $$$3$$$ и $$$6$$$.
  6. И не меньше $$$3$$$ между моментами времени $$$4$$$ и $$$5$$$.

Ниже приведено изменение заполненности комнат для второго примера в первые 10 минут, начиная с 0.