29107번 - Росомаха и стеллаж 다국어

Зверю на день рождения подарили стеллаж с книгами. Стеллаж имеет форму дерева, где вершинам соответствуют полки с книгами, а рёбрам --- соединения полок между собой. В каждой вершине находится несколько (возможно, ноль) книг.

Это не простое дерево, оно обладает следующим свойством: у каждой вершины не более двух детей, и количество книг в каждой вершине равно суммарному количеству книг в её детях. Также известно, что в листьях дерева не более одной книги.

Зверь был очень рад этому подарку, поэтому сразу повесил его на стену. Но Росомаха, проходя мимо, случайно зацепил дерево своими адамантиевыми когтями, и оно упало на пол. Росомаха собрал все книги, которые нашёл, но некоторых явно не хватало, поэтому он решил взять несколько из своей коллекции и добавить их незаметно на полки, чтобы получившееся дерево обладало изначальным свойством. Но после того, как он это сделал, стало только хуже. Теперь надо всё исправить и всё-таки вернуть дереву его изначальное свойство. Зверь скоро вернётся, поэтому Росомахе надо действовать как можно быстрее.

Немного подумав, он понял, что не всегда выгодно только добавлять книги на полки, иногда выгодно их убирать оттуда. За одну секунду Росомаха может либо положить на какую-то полку книгу, либо забрать её с какой-то из полок. Ваша же задача заключается в следующем: помогите Росомахе найти наименьшее время, за которое он сможет получить такими операциями дерево, обладающее тем же свойством, что и дерево, подаренное изначально Зверю на день рождения.

В первой строке входного файла дано число $n$ --- количество вершин в дереве ($1 \le n \le 5000$). Во второй строке входного файла даны $n$ целых чисел $a_i$ ($0 \le a_i \le 5000$) --- количество книг на $i$-й полке. В $i$-й из следующих $n-1$ строк даны два числа $a, b$ ($1 \le a, b \le n$) --- ребро дерева.

Корень дерева находится в вершине с номером 1.

Можно считать, что в коллекции Росомахи бесконечное число книг.

В единственной строке выходного файла выведите минимальное количество секунд, которое понадобится Росомахе, чтобы скрыть свою оплошность.