Деревни лесорубов
В Мидгарде есть n деревень, соединенных сетью дорог. В Мидгарде n - 1 дорога, и по этим дорогам можно от любой деревни добраться до любой другой. Иными словами, сеть дорог образует дерево. Деревня номер 1 является столицей. Мидгардцы добывают много дерева, из которого затем строят корабли. Сейчас правитель Мидгарда хочет за год построить большой флот и отправиться на завоевание новых земель и ресурсов. Для этого, он решил применить следующую стратегию:
Отправить в некоторые деревни наместников. Причем, на простом пути из деревни, в которую отправлен наместник, до столицы не должно находиться другой деревни, в которую тоже отправлен наместник. Обратите внимание, что можно отправить одного наместника в столицу, но в таком случае ни в какую другую деревню наместника уже отправить нельзя.
Наместнику в деревне v отдаются в подчинение все деревни, на простом пути из которых до столицы находится деревня v. В том числе, наместнику отдается в подчинение деревня v.
Для каждой деревни известна величина a[i] - количество кораблей, которые эта деревня построит за год, если она не находится в подчинении ни у какого наместника.
Если в деревне v находится наместник, то он действует следующим образом:
Он выбирает подмножество W деревень, соседних с v, находящихся в его подчинении. В этих деревнях он разворачивает большие мастерские по производству кораблей. Для каждой деревни известно, что если в ней построить мастерскую, то в эту деревню нужно поставлять лес из
b[i]других деревень, и эта мастерская произведетc[i]кораблей за год.Теперь он должен выбрать среди оставшихся деревень в его подчинении ровно Σ
b[u](u ∈ W) деревень, которые будут заниматься поставкой леса в мастерские. В какую конкретную мастерскую будет поставлять лес каждая из них—не так важно.Деревня i, в которой построена мастерская, за год построит
c[i]кораблей.Деревня, которая занимается поставками леса, не будет строить корабли.
Все остальные деревни, в его подчинении, за год построят столько же кораблей, как если бы не находились в его подчинении. То есть, i-я деревня построит
a[i]кораблей за год.
Правитель может разослать любое количество наместников. При условии, что наместники действуют оптимально, определите, какое максимальное количество кораблей может быть суммарно построено всеми деревнями за год.
Входные данные
В первой строке дано одно целое число t (1 ≤ t ≤ 5000) - количество тестов. Далее следует t тестов.
Каждый тест начинается с одного целого числа n (1 ≤ n ≤ 5000) - количество деревень в Мидгарде.
В следующих n строках дано по три целых числа a[i], b[i] и c[i] (1 ≤ a[i], c[i] ≤ 10^9, 1 ≤ b[i] ≤ n) - количество кораблей, которое деревня построит за год, не находясь в подчинении у наместника, количество деревень, которые должны поставлять лес в эту деревню, если в ней построить мастерскую и количество кораблей, которое деревня построит за год, если в ней построить мастерскую.
В следующих n - 1 строках даны описания дорог в Мидгарде. Каждая строка содержит два целых числа v[i], u[i] - номера деревень, соединенных дорогой. Гарантируется, что сеть дорог образует дерево.
Гарантируется, что сумма n во всех тестах не превышает 5000.
Выходные данные
Для каждого теста выведите одно целое число - максимальное количество кораблей, которые все деревни могут суммарно построить за год при правильном распределении наместников.