eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Расстановка копий

Расстановка копий

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Топский хочет построить сеть по доставке информации. Сеть содержит исходный сервер и несколько зеркальных серверов как показано на рисунке. Входные данные находятся в начальном сервере (в корне на рисунке 1), в то время как их копии доставляются в некоторые зеркальные сервера (вершины 2 и 5 на рисунке 1). Когда узел посылает запрос на поиск данных, то он старается найти их местоположение следующим образом.

  1. Проверяем, находится ли копия данных в узле. Если да, то запрос выполнен. Иначе переходим на шаг 2.

  2. Передаем запрос родителю, который совершает шаг 1.

Стоимость выполнения запроса C(v) определяется как сумма весов ребер на пути. Если C(v) не больше верхней границы Q(v), то стоимость поиска считается приемлемой. Топский предполагает также существование неотрицательной стоимости S(v) записи данных в вершине v. Исходный сервер специальный, стоимость сохранения данных в нем равна 0. Топский хочет расположить на серверах копии данных таким образом, чтобы стоимость поиска для всех вершин была приемлемой, а суммарная стоимость записи данных была бы наименьшей.

Входные данные

Первая строка содержит количество тестов t (t20). Каждый тест начинается целым числом n (1 n1000), которое указывает на количество серверов. Далее идут n строк, каждая из которых содержит четыре целых числа F_v (0F_vn), Q_v, S_v и W_v (0Q_v, S_v, W_v10^5). В строке i (1in), F_v обозначает отца вершины i (если F_v равно 0, то i является исходным сервером, Q_v равно -1, S_v равно 0 и W_v равно 0), Q_v является верхней границей стоимости поиска, S_v равно стоимости записи данных в вершине i, а W_v равно весу ребра, соединяющего вершины i и F_v.

Выходные данные

Для каждого теста в отдельной строке вывести минимальную стоимость затрат на хранение данных.

Пример

Входные данные #1
AGCT
GCAT
Выходные данные #1
3
1 2
2 3
3 3