Special Nodes

Time limit2sMemory limit128 MB

Summary
In a rooted tree where child weights exceed parent weights, mark vertices special or ordinary to minimize the total of each ordinary vertex's weight minus its nearest special ancestor's weight.
Level

Medium7 of 10

Topics
Dynamic programming, Tree, DFS, Recursion
Solved
No attempts yet

Problem

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.

Input

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.

Output

Print the minimum possible sum of recalculated weights.

Examples1

  1. Example 1

    Input
    7 1
2 4 5 3 6 7 8
1 2
1 3
1 4
2 5
2 6
6 7
    Expected output
    19