401432: GYM100451 A Decorating the Tree

Every year Vasya has winter holidays from January, 1 for a week or more. He considers it as the most boring time of the year. His university is closed, exams still not started, and TV shows only the oldest movies. Luckily, Vasya has a New Year tree at home and he constantly invents more complicated ways to decorate his tree.

Vasya wants to use n sets and put them to n different places of his tree. More formally, he represnted his New Year tree as a graph theory tree with n nodes. Vasya wants to put exactly one decoration set to every node of the tree. Decoration set for node v_i must be of size c_i.

Vasya can buy decoration sets in the shop next to his house. Any decoration set is defined by two parameters: its size and its base. Such a set consists of size balls with radii base, base + 1, ..., base + size - 1. The set costs base + size - 1 rubles, i. e. the price only depends on the radius of the largest ball. For any given positive integers size and base the shop can quickly deliver any amount of decoration sets.

Vasya has a special requirement to the decoration. He does not want two decoration sets on adjacent nodes to share a ball of the same size. At the same time, he has nothing against having same balls or even same decoration sets on nodes which are not connected with an edge.

Please note, that Vasya has to buy exactly n decoration sets. No decoration set can be split, and no two decoration sets can be merged together.

Please help Vasya to decorate his tree at a minimum cost.

First line of the input contains a single integer, n (1 ≤ n ≤ 2000). Next line contains n integers, c_i describes required size of decoration set for i-th node (1 ≤ c_i ≤ 10⁹). Next n - 1 lines describe edges. Each line has format "u v" (0 ≤ u, v ≤ n - 1) and means that nodes u and v are connected with the edge.

Print minimum decorating cost on the single line.

5
5 1 5 1 2
0 1
1 2
2 3
2 4

17

2
1 2
0 1

4