Села лісорубів#11033

Села лісорубів

2 секунди

128 мегабайтів

Дуже складна

У Мідгарді є $n$ сіл, з'єднаних мережею доріг. У Мідгарді $n - 1$ n - 1 дорога, і по цих дорогах можна дістатися від будь-якого села до будь-якого іншого. Іншими словами, мережа доріг утворює дерево. Село номер $1$ є столицею. Мідгардці добувають багато дерева, з якого потім будують кораблі. Зараз правитель Мідгарда хоче за рік побудувати великий флот і вирушити на завоювання нових земель і ресурсів. Для цього він вирішив застосувати таку стратегію:

Відправити в деякі села намісників. Причому, на простому шляху з села, в яке відправлений намісник, до столиці не повинно знаходитися іншого села, в яке теж відправлений намісник. Зверніть увагу, що можна відправити одного намісника в столицю, але в такому випадку ні в яке інше село намісника вже відправити не можна.

Наміснику в селі $v$ віддаються в підпорядкування всі села, на простому шляху з яких до столиці знаходиться село $v$ . В тому числі, наміснику віддається в підпорядкування село $v$ .

Для кожного села відома величина $a_{i}$ a_i - скільки кораблів це село побудує за рік, якщо воно не знаходиться в підпорядкуванні у жодного намісника.

Якщо в селі $v$ знаходиться намісник, то він діє наступним чином:

Він обирає підмножину $W$ сіл, сусідніх з $v$ , що знаходяться в його підпорядкуванні. У цих селах він розгортає великі майстерні з виробництва кораблів. Для кожного села відомо, що якщо в ньому побудувати майстерню, то в це село потрібно постачати ліс з $b_{i}$ b_i інших сіл, і ця майстерня виробить $c_{i}$ c_i кораблів за рік.
Тепер він повинен обрати серед решти сіл в його підпорядкуванні рівно $\sum b_{u}$ \sum b_u ( $u \in W$ u \in W) сіл, які будуть займатися постачанням лісу в майстерні. В яку конкретну майстерню буде постачати ліс кожне з них — не так важливо.
Село $i$ , в якому побудована майстерня, за рік побудує $c_{i}$ c_i кораблів.
Село, яке займається постачанням лісу, не буде будувати кораблі.
Всі інші села, в його підпорядкуванні, за рік побудують стільки ж кораблів, як якщо б не знаходилися в його підпорядкуванні. Тобто, $i$ -те село побудує $a_{i}$ a_i кораблів за рік.

Правитель може розіслати будь-яку кількість намісників. За умови, що намісники діють оптимально, визначте, яку максимальну кількість кораблів може бути сумарно побудовано всіма селами за рік.

Вхідні дані

У першому рядку дано одне ціле число $t$ ( $1 \leq t \leq 5000$ 1 \le t \le 5000) - кількість тестів. Далі слідує $t$ тестів.

Кожен тест починається з одного цілого числа $n$ ( $1 \leq n \leq 5000$ 1 \le n \le 5000) - кількість сіл у Мідгарді.

У наступних $n$ рядках дано по три цілі числа $a_{i}$ a_i, $b_{i}$ b_i і $c_{i}$ c_i ( $1 \leq a_{i}, c_{i} \leq 1 0^{9}$ 1 \le a_i, c_i \le 10^9, $1 \leq b_{i} \leq n$ 1 \le b_i \le n) - скільки кораблів село побудує за рік, не знаходячись в підпорядкуванні у намісника, кількість сіл, які повинні постачати ліс в це село, якщо в ньому побудувати майстерню і скільки кораблів село побудує за рік, якщо в ньому побудувати майстерню.

У наступних $n - 1$ n - 1 рядках дано описи доріг у Мідгарді. Кожен рядок містить два цілі числа $v_{i}$ v_i, $u_{i}$ u_i - номери сіл, з'єднаних дорогою. Гарантується, що мережа доріг утворює дерево.

Гарантується, що сума $n$ у всіх тестах не перевищує $5000$ .

Вихідні дані

Для кожного тесту виведіть одне ціле число - максимальну кількість кораблів, які всі села можуть сумарно побудувати за рік при правильному розподілі намісників.

Приклади

Приклад 1