Задача #0273

Вам дано дерево состоящее из \(N\) узлов. Каждый узел в дереве имеет неотрицательное значение, которое означает, сколько энергии потребуется для прохождения через этот узел.

\(\text{Вес}(A,B)\) это сумма значений на всех узлах (кроме узлов \(A\) и \(B\)),которые проходят по пути от узла \(A\) к узлу \(B\).

У вас есть возможность изменить значения в узлах дерева на произвольное неотрицательное значение.

Вы должны уточнить какое минимальное количество значений узлов вы должны изменить для того чтобы равенство  \(\sum_{A=1}^{N} \sum_{B=1}^{N} \text{Вес}(A,B) = 0\)  было верным.

Первая строка входного файла содержит одно целое число \(T(1 \le T \le 10)\) количество тестов.

Для каждого теста:

В первой строке дано одно целое число \(N(1 \le N \le 10^5)\) - количество узлов дерева.

В следующих \(N-1\) строках вводятся пары \(U\) и \(V(1 \le U, V \le N,  U \neq V)\), которые представляют наличие пути между узлами \(U\) и \(V\) дерева.

В последней строке \(N\) целых чисел в диапазоне \([0, 10^9]\) являются значениями, заданными в узлах дерева.

В отдельной строке для каждого теста напечатайте какое минимальное число значений узлов нужно изменить на целые неотрицательные числа чтобы равенство \(\sum_{A=1}^{N} \sum_{B=1}^{N} \text{Вес}(A,B) = 0\) было верным.