Tree Coloring

A rooted tree has N nodes, and every node has a weight. Let C\[i] be the weight of node i.

You will color all nodes one at a time. If node i is the F\[i]-th node colored, the cost of coloring it is C\[i] * F\[i]. The total cost is the sum of the costs of all nodes.

Before a node can be colored, its parent must already be colored. Therefore, the root must be colored first. Find the minimum possible total cost while following this rule.

The first line contains two integers N and R, the number of nodes in the tree and the root node. (1 ≤ N ≤ 1,000, 1 ≤ R ≤ N)

The second line contains C\[1], C\[2], ..., C\[N] in order.

Each of the next N - 1 lines contains two positive integers U and V. This means that node U is the parent of node V.

Print the minimum total cost needed to color the entire tree.

If the nodes are colored in the order 1, 3, 5, 2, 4, the step costs are 1 * 1, 2 * 1, 3 * 4, 4 * 2, and 5 * 2, for a total cost of 33.