409521: GYM103608 D Необычная ловушка
Description
Загадочник придумал новую ловушку для жителей Готэм–сити. По плану злодея, ловушка будет состоять из $$$n$$$ помещений, соединенных переходами так, чтобы из любого помещения $$$u$$$ всегда был единственный способ добраться в помещение $$$v$$$.
Для перемещения между комнатами нужно будет использовать специальный лифт, который может перемещаться по всем переходам ловушки. Одновременно лифт вмещает не больше $$$b$$$ людей, и когда лифт хотя бы с одним человеком внутри переезжает из помещения $$$u_i$$$ в помещение $$$v_i$$$, он теряет $$$w_i$$$ прочности. Лифт не теряет прочность, если в нем нет людей во время перемещения.
Загадочник планирует поделить всех своих жертв на $$$m$$$ групп так, чтобы в группе $$$i$$$ было $$$c_i$$$ человек, которые изначально находятся в комнате $$$x_i$$$, и обязаны добраться до комнаты $$$y_i$$$ (разумеется, используя лифт). При этом людям не запрещается временно высаживаться в произвольных местах пути и ждать перед тем, как продолжить движение.
Супер–злодей хочет выбрать такую прочность лифта, чтобы лифт мог доставить всех людей в нужные комнаты, но гарантированно разрушился (то есть его прочность упала до $$$0$$$) сразу после этого. Для этого он хочет найти минимальные возможные повреждения, которые может получить лифт, перемещая людей. Как опытный злодей, Загадочник справится с этой задачей, а справитесь ли вы?
Входные данныеВ первой строке ввода через пробел даны три целых числа $$$n$$$, $$$m$$$ и $$$b$$$ — количество помещений в ловушке, количество групп людей и максимальная вместимость лифта ($$$2 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant m \leqslant 2 \cdot 10^5$$$; $$$1 \leqslant b \leqslant 10^9$$$).
В следующих $$$n - 1$$$ строках дается описание комнат ловушки, между которыми есть переходы. В строчке $$$i$$$ даются три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$, означающие, что между комнатами $$$u_i$$$ и $$$v_i$$$ есть переход для лифта, наносящий лифту $$$w_i$$$ повреждений ($$$1 \leqslant u_i, v_i \leqslant n$$$; $$$0 \leqslant w_i \leqslant 10^4$$$). Гарантируется, что от любой комнаты можно добраться по переходам до любой другой.
В следующих $$$m$$$ строках дается описание групп людей. Описание группы номер $$$i$$$ — три целых числа $$$x_i$$$, $$$y_i$$$ и $$$c_i$$$ — номера стартовой и конечной комнат, и количество людей в группе ($$$1 \leqslant x_i, y_i \leqslant n$$$; $$$1 \leqslant c_i \leqslant 10^9$$$).
Выходные данныеВыведите единственное число — минимальную величину повреждений, которые получит лифт после того, как все люди сбегут из ловушки Загадочника.
Система оценкиБаллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 9 | $$$n, m, b \leqslant 3$$$; $$$c_i \leqslant 3$$$ для всех $$$i$$$ | – | полная |
2 | 14 | $$$n, m, b \leqslant 50$$$; $$$c_i \leqslant 50$$$ для всех $$$i$$$ | 1 | полная |
3 | 10 | $$$n \leqslant 10^4$$$; $$$c_i \leqslant 10^4$$$ для всех $$$i$$$; $$$b = 10^9$$$ | – | полная |
4 | 16 | каждое помещение соединено только с одним или двумя другими | – | полная |
5 | 19 | $$$n, m \leqslant 500 $$$ | 2 | полная |
6 | 12 | $$$n \leqslant 5000 $$$ | 5 | первая ошибка |
7 | 20 | нет | 1 – 6 | первая ошибка |
4 3 5 3 2 3 3 4 0 4 1 2 1 2 9 2 4 7 3 4 12Выходные данные
16Входные данные
7 3 5 2 1 2 3 1 1 3 4 3 3 5 0 5 6 4 5 7 0 2 4 11 1 7 8 4 5 3Выходные данные
22Примечание
В первом примере комнаты связаны по цепочке $$$2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 1$$$. Одна из возможных последовательностей действий выглядит так:
- отвезти $$$5$$$ людей из второй комнаты в четвертую (потратив $$$3$$$ прочности);
- вернуться во вторую, забрать $$$2$$$ человека из второй комнаты, и по пути в четвертую — подобрать еще $$$3$$$ человека в третьей (потратив $$$3$$$ прочности);
- дальше доехать до первой, отвезти $$$5$$$ людей из нее во вторую (за $$$5$$$ прочности), и на обратном пути в первую подвести $$$5$$$ людей из третьей в четвертую (за $$$0$$$ прочности);
- повторить последний шаг для оставшихся $$$4$$$ людей вместо $$$5$$$ (еще $$$5$$$ прочности).
Во втором примере один из оптимальных вариантов выглядит следующим образом: сначала доставить всех людей до комнаты номер $$$3$$$ (при чем люди, двигающиеся из комнаты номер $$$2$$$, должны будут взять себе попутчиков в комнате $$$1$$$), а после развести их по нужным комнатам в максимально возможных группах.