Необычная ловушка

Автор задачи и разработчик: Константин Бац.

Данная в задаче система комнат представляет из себя дерево, то есть связный ациклический неориентированный граф.

Из того, что ловушка позволяет высаживать людей из лифта, следует, что человек по пути из комнаты $$$x$$$ в комнату $$$y$$$ может посетить комнаты на пути из $$$x$$$ в $$$\mathrm{lca}(x, y)$$$ и пути из $$$\mathrm{lca}(x, y)$$$ в $$$y$$$. Здесь и далее $$$\mathrm{lca}$$$ — ближайший к вершинам $$$x$$$ и $$$y$$$ общий предок.

Для решения первой и второй подзадач можно было явно просимулировать перемещение людей по вершинам и рёбрам графа. Давайте для всех вершин посчитаем минимальное количество лифтов, чтобы перевезти заложников в каждую из сторон. Ответ на задачу — $$$\sum\limits_{u\to v} w_{u\to v} \cdot \mathrm{cnt}_{u\to v}$$$, где $$$\mathrm{cnt}$$$ — минимальное количество лифтов, необходимое, чтобы перевезти всех людей по ребру $$$u\to v$$$.

Ограничения третьей подзадачи указывали на то, что вместимость лифта позволяет перевезти всех людей за одну поездку. Таким образом, для каждого рёбра в одну и другую сторону нужно было понять, поедет ли кто-то по нему, и если это так, добавить в ответ $$$w_{u\to v}$$$ этого ребра.

В подзадаче четыре каждая комната соединялась с одной или двумя, поэтому граф на самом деле представляется в виде цепочки вершин. Это отличает группу от других тем, что весь граф можно представить в виде прямой, а путь из $$$x$$$ в $$$y$$$ как отрезок этой прямой. Пользуясь деревом отрезков или деревом Фенвика можно было, прибавляя $$$c_i$$$ на отрезке, для каждого ребра посчитать сколько раз его пересекут. Дальше для каждого ребра почитать минимальное количество поездок лифта, чтобы перевезти всех людей и с учётом всех $$$w_i$$$ посчитать ответ.

На самом деле, решение задачи в общем случае отличается лишь тем, что $$$c_i$$$ нужно прибавлять не на отрезке, а в дереве.

Для пятой подзадачи можно было на каждую из $$$m$$$ групп найти $$$\mathrm{lca}$$$, затем явно выделить путь из $$$x$$$ в $$$y$$$ и за $$$\mathcal{O}(n^2)$$$ к каждому ребру для нужного направления прибавить $$$c_i$$$. Время работы такого решения равно $$$\mathcal{O}(m\cdot n^2)$$$.

Решение задачи на полный балл предполагало подсчёт суммы в поддереве. Нам нужно прибавлять $$$c_i$$$ на пути от $$$u$$$ до $$$p$$$, где $$$p$$$ — какой-то предок $$$u$$$. Давайте в каждой вершине хранить два числа: $$$e$$$ и $$$f$$$. Рассмотрим группу $$$i$$$, выделим путь из $$$u$$$ в $$$v$$$, и пусть $$$\mathrm{lca}(u, v) = p$$$. Прибавим к $$$e_v$$$ и $$$f_v$$$ величину $$$c_i$$$ и вычтем из $$$e_p$$$ и $$$f_p$$$ величину $$$c_i$$$. После рассмотрения всех групп людей, прибавим к $$$e_v$$$ и $$$f_v$$$ сумму $$$e$$$ и $$$f$$$ в поддереве соответственно.