Special Nodes

A rooted tree T with n (1 <= n <= 1,000) vertices is given. Each vertex v has a weight w_v (1 <= w_v <= 50,000). When the tree is viewed from the given root, every vertex has a weight greater than its parent's weight.

Each vertex is chosen to be either special or ordinary. The root must be special.

The recalculated weight is defined as follows.

• If vertex v is special, its new weight is its original weight w_v.
• If vertex v is ordinary, let u be the closest special ancestor of v. Its new weight is w_v - w_u.

Choose the special vertices so that the sum of all recalculated weights is minimized.

The first line contains n and the number of the root vertex. The second line contains the weights of vertices 1 through n. Each of the next n-1 lines contains two vertices connected by an edge in the tree.

Print the minimum possible sum of recalculated weights.