Tree Pruning to Minimize Instability

In Borova Suma on the opposite riverbank a magical tree still stands – a tree with N nodes. Each node v carries an integer a_v. The tree is rooted at node 1. We say a (non‐empty) tree T is k-good if the following two conditions hold:

• For every edge connecting a parent u to its child v in T, the labels satisfy \(a_v = (a_u+1) \bmod k\). That is, if a_u is not equal to \(k-1\) then a_v must equal a_u+1; if a_u = k-1 then a_v must equal 0.
• Every node in T satisfies \(a_v < k\).

For every natural number k there is an intrinsic instability of a k-good tree defined as \(f(k)=k\>.

Ivan, wielding his magical axe, has decided to chop some branches. In other words, he will remove a subset of edges from the given tree. Each remaining connected component becomes a subtree. For each such component, Ivan will choose a number k such that the component is k-good (note that if the component’s nodes have maximum value m then one valid choice is \(k=m+1\); in fact, the cost of a component is defined to be \(k\) and one always may choose the minimal possible \(k\)).

The instability of a given pruning is defined as the sum, over every component, of \(f(k)\) (recall \(f(k)=k\)). Your task is to help Ivan determine the minimum possible overall instability over all choices of which edges to remove and for each component which valid k to choose.

Note: A single node is trivially k-good if you choose \(k=a+1\> because there are no edges to check.

inputFormat

The input begins with an integer N indicating the number of nodes in the tree. The next line contains N integers, where the i-th integer is a_i — the label on node i.

Then follow N-1 lines, each containing two integers u and v indicating that there is an edge between nodes u and v. It is guaranteed that the given graph is a tree and that the tree is rooted at node 1.

outputFormat

Output a single integer — the minimum possible instability (i.e. the minimum sum of k over all components after an optimal pruning).

sample

3
0 1 2
1 2
2 3

3