Автор задачи и разработчик: Константин Бац
Переформулируем задачу: дано взвешенное дерево с вершинами-комнатами и ребрами-трубами. Корень дерева находится в самой нижней комнате, длина каждого ребра — разность между глубинами соответствующих вершин. Также в каждой вершине дерева изначально было некоторое количество льда, которое моментально тает от пришедшей сверху воды и начинает стекать вниз по трубе.
Ограничения первой группы тестов позволяли явно просимулировать то, как меняется уровень воды в комнатах и на основании этого ответить на запросы. Для каждой комнаты будем хранить четыре значения — флаг «растаял ли лед», текущий уровень воды, и состояние воды в трубе, ведущей из комнаты вниз. Состояние воды в трубе описывается тем, до какого нижнего уровня она уже опустилась, и, если вода в комнате уже закончилась, то на каком уровне находится самая верхняя оставшаяся единица воды в трубе.
Будем за один шаг увеличивать время на $$$1$$$, и обрабатывать комнаты в порядке увеличения глубины:
Стимуляцию стоит проводить до тех пор, пока вода не прекратит движение. Для каждой комнаты можно в любой удобной структуре данных хранить «график» количества воды в ней. Если посчитать на нем суффиксные суммы, на запросы можно будет отвечать за $$$\mathcal{O}(1)$$$. Время работы такого решения — $$$\mathcal{O}(T \cdot n + m)$$$, где $$$T$$$ — время, за которое вода из комнат дотечет до самой глубокой комнаты и вытечет из нее.
Для решения следующих подгрупп следует обратить внимание на то, как изменяется уровень воды в комнатах, которые находятся под землей. Для начала можно (например, по индукции по глубине) доказать, что лед в комнате на глубине $$$d_i$$$ тает ровно в момент времени $$$d_i$$$, потому что вода «непрерывно» движется вниз со скоростью $$$1$$$.
Более того, вода из всех труб, ведущих в конкретную комнату, начнет поступать в нее одновременно, после чего скорость роста воды в ней будет равна $$$|\mathtt{children}(i)| - 1$$$. Опять же, по индукции, можно доказать, что каждая комната является непустой в течение непрерывного промежутка времени. Поэтому:
Во второй группе в качестве дерева был дан бамбук. Это позволяет заметить, что вся вода, которая попадает в комнату, сразу же уходит ниже, и в комнате не скапливается (скорость роста воды равна $$$0$$$). Пользуясь этим, можно было для каждой комнаты в порядке увеличения глубины подсчитать $$$h_i^{\mathrm{stop}}$$$ — время, в которое вода прекратит поступать из комнаты сверху. Как уже было сказано, лед в комнате $$$i$$$ тает в момент $$$d_i$$$, поэтому с момента $$$d_i$$$ минут по $$$h_i^{\mathrm{stop}}$$$ минут уровень воды будет в точности равен $$$a_i$$$, после этого в течении $$$a_i$$$ минут он будет уменьшаться со скоростью $$$1$$$. Это позволяет отвечать на запросы за время $$$\mathcal{O}(1)$$$.
В третьей группе было дано полное двоичное дерево, и все трубы были равной длинны. Это ограничение гарантировало, что для всех вершин «на одном уровне» уровень воды будет меняться одинаково. И для каждой вершины изменение уровня воды будет проходить в два этапа: сперва уровень будет расти со скоростью $$$1$$$, а затем, когда вода перестанет течь из верхних комнат, уровень воды будет уменьшаться со скоростью $$$1$$$. Для ответов на запросы можно было вывести формулу, соответствующую такому процессу.
В подзадачах четыре и пять можно было в той или иной мере неэффективно применить идею полного решения.
Как уже было сказано выше, уровень воды в комнатах сперва монотонно возрастает, а потом монотонно убывает. Ясно, что изменение уровня воды напрямую зависит от скорости поступления воды в комнату. Если в комнату поступает вода из $$$v$$$ труб, то за одну минуту уровень воды повышается на $$$v - 1$$$. Поэтому максимальный уровень воды достигается, когда все трубы, кроме одной, перестают давать воду.
Для полного решения следовало для каждой комнаты создать массив событий, описывающих изменение скорости роста. Обрабатывая комнаты в порядке возрастания их глубины, несложно определить, в какие моменты будет меняться скорость: если комната $$$i$$$ станет полностью пустой в момент времени $$$t$$$, то в момент времени $$$t + d_{b_i} - d_i$$$ скорость роста уровня воды в комнате $$$b_i$$$ уменьшится на $$$1$$$. Все такие события, плюс событие «в момент времени $$$d_i$$$ скорость роста становится равна $$$|\mathtt{children}(i)|$$$», можно отсортировать по возрастанию момента времени, после чего посчитать на них префиксные суммы скоростей с учетом длин интервалов времени (это и будут уровни воды в моменты изменения скорости).
Тогда для ответа на запрос достаточно с помощью бинпоиска по «растущей» части массива событий найти первый момент времени, в который уровень достигает $$$x$$$, и вычесть его из последнего момента, когда уровень равен $$$x$$$. Последний момент найти еще проще — он случается, когда все трубы над комнатой опустели, и уровень воды в комнате снижается. Зная момент последнего события и уровень воды на этот момент, можно найти интересующий нас конец интервала. Такое решение будет работать за $$$\mathcal{O}((m + n) \cdot \log n)$$$.