Розміщення копій#2189
Топський хоче побудувати мережу доставки контенту. Вона складається з оригінального сервера та кількох серверів-дзеркал, як показано на рисунку . Оригінальні дані зберігаються на оригінальному сервері (корінь на рисунку ), а копії можуть зберігатися на деяких із серверів-дзеркал (вузли та на рисунку ). Коли вузол надсилає запит на дані, він намагається знайти дані наступним чином.
Перевірити, чи є копія у власному розташуванні. Якщо так — запит задовольняється. Інакше перейти до кроку .
Переслати запит до батьківського вузла та дозволити йому виконати крок .
Вартість виконання запиту визначається як сума ваг ребер уздовж шляху. Якщо не перевищує верхню межу , така вартість вважається прийнятною. Топський враховує невід'ємну вартість зберігання — це вартість зберігання даних у вузлі . Зверніть увагу, що оригінальний сервер особливий: вартість зберігання на ньому дорівнює .
Топський хоче розмістити копії так, щоб задовольнити обмеження по вартості доступу для всіх вузлів, а загальна вартість зберігання була мінімальною.
У першому рядку знаходиться ціле число (1 \leq t \leq 20) — кількість тестових випадків. Кожен тестовий випадок починається з цілого числа (1 \leq n \leq 1000) — кількість серверів. Потім слідують рядків. Кожний рядок містить чотири цілих числа: F_v (0 \leq F_v \leq n), Q_v, S_v, і W_v (0 \leq Q_v, S_v, W_v \leq 10^5). У рядку (1 \leq i \leq n), F_v — це батьківський вузол для вузла (якщо F_v дорівнює , то вузол є оригінальним сервером, а Q_v, S_v та W_v для цього вузла дорівнюють , і відповідно); Q_v — верхня межа вартості доступу, S_v — вартість зберігання у вузлі , а W_v — вага ребра між вузлом та його батьком F_v.
Для кожного тестового випадку виведіть у окремому рядку мінімальну загальну вартість зберігання.
Приклад 1