题目描述

给定一棵有 $N$ 个节点的树，树根为 $R$ ，现在欲给这棵树的所有节点染色。给点 $i$ 染色的代价为 $t\cdot C_i$，其中 $t$ 代表这是第几次染色，$C_i$ 是给定的权值。

此外，染一个点前，它的父节点必须已染好色（所以根节点 $R$ 一定最先被染色）。求染完这棵树最小的代价。

输入格式

第一行是两个整数 $N$ 和 $R$，表示树的节点数和树根的编号。

第二行是 $N$ 个整数，第 $i$ 个整数代表 $C_i$，含义见题面。

下来 $N-1$ 行，每行两个整数 $u,v$，表示 $u$ 是 $v$ 的父亲。

输出格式

输出一行一个整数，表示最小代价。

输入输出样例 #1

输入 #1

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

输出 #1

33

说明/提示

$1\leq R \leq N\leq 10^3$， $1\leq C_i\leq 500$。

$\small{\text{Statement fixed by @Starrykiller.}}$