Color a Tree

给定一棵有 $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$。 $\small{\text{Statement fixed by @Starrykiller.}}$

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3646 [PDF](https://uva.onlinejudge.org/external/12/p1205.pdf)

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

33