| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
В Мидгарде есть $n$ деревень, соединенных сетью дорог. В Мидгарде $n - 1$ дорога, и по этим дорогам можно от любой деревни добраться до любой другой. Иными словами, сеть дорог образует дерево. Деревня номер 1ドル$ является столицей. Мидгардцы добывают много дерева, из которого затем строят корабли. Сейчас правитель Мидгарда хочет за год построить большой флот и отправиться на завоевание новых земель и ресурсов. Для этого, он решил применить следующую стратегию:
Правитель может разослать любое количество наместников. При условии, что наместники действуют оптимально, определите, какое максимальное количество кораблей может быть суммарно построено всеми деревнями за год.
В первой строке дано одно целое число $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円$.
Для каждого теста выведите одно целое число --- максимальное количество кораблей, которые все деревни могут суммарно построить за год при правильном распределении наместников.
3 3 1 1 10 1 1 9 5 1 11 1 2 2 3 4 2 4 9 2 2 6 1 4 7 4 4 8 1 2 2 3 1 4 7 3 1 10 2 4 6 3 2 8 2 3 4 1 1 9 2 1 6 1 2 4 1 2 2 3 3 4 2 5 5 6 5 7
14 10 22