题目描述

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

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

输入格式

本题有多组测试数据。

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

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

接下来 $\left(N-1\right)$ 行，每行两个整数 $u,v$，表示 $u$ 是 $v$ 的父亲。

数据结尾的标志是 $N=R=0$。你并不需要处理这组数据。

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

输出格式

对于每组数据，输出一行一个整数，表示最小代价。

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

33