28622번 - Подземная лаборатория 다국어

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