Дерево#4248
Шановний учаснику, ви, напевно, знаєте, що таке дерево. У структурі даних дерево визначається як граф, у якому між будь-якими двома вершинами існує лише один шлях. Розгляньмо просте завдання. Нехай вершини дерева мають вагу, а вага дерева дорівнює сумі ваг усіх його вершин. Потрібно розділити дерево на два піддерева так, щоб різниця між їх вагами була мінімальною.
Перший рядок містить кількість тестів .
Кожен тест починається з кількості вершин у дереві (2 \leq N \leq 10000). Далі йдуть цілих чисел W_i (1 \leq W_i \leq 1000) — ваги вершин з номерами від до .
Потім слідують N-1 рядків, кожен з яких містить два цілі числа A_i і B_i (1 \leq A_i, B_i \leq N), що задають ребро дерева.
Для кожного тесту виведіть одне ціле число — найменшу різницю ваг.
Приклад 1