28806번 - Деревни лесорубов 다국어

В Мидгарде есть $n$ деревень, соединенных сетью дорог. В Мидгарде $n - 1$ дорога, и по этим дорогам можно от любой деревни добраться до любой другой. Иными словами, сеть дорог образует дерево. Деревня номер $1$ является столицей. Мидгардцы добывают много дерева, из которого затем строят корабли. Сейчас правитель Мидгарда хочет за год построить большой флот и отправиться на завоевание новых земель и ресурсов. Для этого, он решил применить следующую стратегию:

• Отправить в некоторые деревни наместников. Причем, на простом пути из деревни, в которую отправлен наместник, до столицы не должно находиться другой деревни, в которую тоже отправлен наместник. Обратите внимание, что можно отправить одного наместника в столицу, но в таком случае ни в какую другую деревню наместника уже отправить нельзя.
• Наместнику в деревне $v$ отдаются в подчинение все деревни, на простом пути из которых до столицы находится деревня $v$. В том числе, наместнику отдается в подчинение деревня $v$.
• Для каждой деревни известна величина $a_i$ --- количество кораблей, которые эта деревня построит за год, если она не находится в подчинении ни у какого наместника.
• Если в деревне $v$ находится наместник, то он действует следующим образом:​​​​​​​
  • Он выбирает подмножество $W$ деревень, соседних с $v$, находящихся в его подчинении. В этих деревнях он разворачивает большие мастерские по производству кораблей. Для каждой деревни известно, что если в ней построить мастерскую, то в эту деревню нужно поставлять лес из $b_i$ других деревень, и эта мастерская произведет $c_i$ кораблей за год.
  • Теперь он должен выбрать среди оставшихся деревень в его подчинении ровно $\sum\limits_{u \in W} b_u$ деревень, которые будут заниматься поставкой леса в мастерские. В какую конкретную мастерскую будет поставлять лес каждая из них --- не так важно.
  • Деревня $i$, в которой построена мастерская, за год построит $c_i$ кораблей.
  • Деревня, которая занимается поставками леса, не будет строить корабли.
  • Все остальные деревни, в его подчинении, за год построят столько же кораблей, как если бы не находились в его подчинении. То есть, $i$-я деревня построит $a_i$ кораблей за год.

Правитель может разослать любое количество наместников. При условии, что наместники действуют оптимально, определите, какое максимальное количество кораблей может быть суммарно построено всеми деревнями за год.

В первой строке дано одно целое число $t$ --- количество тестов ($1 \le t \le 5\,000$). Далее следует $t$ тестов.

Каждый тест начинается с одного целого числа $n$ --- количество деревень в Мидгарде ($1 \le n \le 5000$).

В следующих $n$ строках дано по три целых числа $a_i$, $b_i$ и $c_i$ --- количество кораблей, которое деревня построит за год, не находясь в подчинении у наместника, количество деревень, которые должны поставлять лес в эту деревню, если в ней построить мастерскую и количество кораблей, которое деревня построит за год, если в ней построить мастерскую ($1 \le a_i, c_i \le 10^9$; $1 \le b_i \le n$).

В следующих $n - 1$ строках даны описания дорог в Мидгарде. Каждая строка содержит два целых числа $v_i$, $u_i$ --- номера деревень, соединенных дорогой. Гарантируется, что сеть дорог образует дерево.

Гарантируется, что сумма $n$ во всех тестах не превышает $5\,000$.

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