You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

一颗树有 $n$ 个节点，这些节点被标号为：$1,2,3…n$，每个节点 $i$ 都有一个权值 $A[i]$。

现在要把这棵树的节点全部染色，染色的规则是：

根节点 $R$ 可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。

每次染色的代价为 $T \times A[i]$，其中 $T$ 代表当前是第几次染色。

求把这棵树染色的最小总代价。

Input Format

第一行包含两个整数 $n$ 和 $R$，分别代表树的节点数以及根节点的序号。

第二行包含 $n$ 个整数，代表所有节点的权值，第 $i$ 个数即为第 $i$ 个节点的权值 $A[i]$。

接下来 $n-1$ 行，每行包含两个整数 $a$ 和 $b$，代表两个节点的序号，两节点满足关系： $a$ 节点是 $b$ 节点的父节点。

除根节点外的其他 $n-1$ 个节点的父节点和它们本身会在这 $n-1$ 行中表示出来。

同一行内的数用空格隔开。

Output Format

输出一个整数，代表把这棵树染色的最小总代价。

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

33

Hint

数据范围

$ 1 \le n \le 1000 $，
$ 1 \le A [i] \le 1000 $