描述

Bob 对树的数据结构非常感兴趣。树是一个有向图，其中有一个特殊的节点被单独挑选出来，称为树的“根”，并且从根到其他每个节点都有唯一的一条路径。

Bob 打算用一支笔给树的所有节点上色。树有 $N$ 个节点，这些节点编号为 1, 2, ..., N。假设给一个节点上色需要 1 个单位的时间，并且在完成一个节点的上色后，他被允许给另一个节点上色。此外，他只有在给其父节点上色后才被允许给一个节点上色。显然，Bob 只被允许在第一次尝试时给根节点上色。

每个节点都有一个“上色成本因子”，$C_i$。每个节点的上色成本取决于 $C_i$ 和 Bob 完成给该节点上色的时间。在开始时，时间设置为 0。如果给节点 $i$ 上色的完成时间是 $F_i$，那么节点 $i$ 的上色成本是 $C_i \times F_i$。

例如，一个有五个节点的树如图1所示。每个节点的上色成本因子分别是 1, 2, 1, 2 和 4。Bob 可以按照 1, 3, 5, 2, 4 的顺序给树上色，总上色成本最小，为 33。

给定一棵树和每个节点的上色成本因子，请帮助 Bob 找到给所有节点上色的最小可能总上色成本。

输入

输入包含多个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $R$（$1 \leq N \leq 1000$，$1 \leq R \leq N$），其中 $N$ 是树中的节点数量，$R$ 是根节点的编号。第二行包含 $N$ 个整数，第 $i$ 个整数是 $C_i$（$1 \leq C_i \leq 500$），节点 $i$ 的上色成本因子。接下来的 $N-1$ 行每行包含两个用空格分隔的节点编号 $V_1$ 和 $V_2$，它们是树中一条边的端点，表示 $V_1$ 是 $V_2$ 的父节点。任何边都不会被列出两次，且所有边都会被列出。

一个测试用例 $N = 0$ 和 $R = 0$ 表示输入结束，不应被处理。

输出

对于每个测试用例，输出一行，包含 Bob 给所有节点上色所需的最小总上色成本。

输入数据 1

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

输出数据 1

33

来源

北京2004