题目描述

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

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

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

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

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

输入格式

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

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

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

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

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

输出格式

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

样例

输入数据

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

输出数据

33

提示

$\red{1≤n≤1000}$,

$\red{1≤A[i]≤1000}$