#3238. 给树染色 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

一颗树有 n 个节点,这些节点被标号为:1,2,3…n,每个节点 i 都有一个权值 A[i]。

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

根节点R可以随时被染色;对于其他节点,在被染色之前它的父亲节点必须已经染上了色。

每次染色的代价为T*A[i],其中T代表当前是第几次染色。

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

输入格式

第一行包含两个整数 n 和 R ,分别代表树的节点数以及根节点的序号。

第二行包含 n 个整数,代表所有节点的权值,第 i 个数即为第 i 个节点的权值 A[i]。

接下来n-1行,每行包含两个整数 a 和 b ,代表两个节点的序号,两节点满足关系: a 节点是 b 节点的父节点。

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

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

输出格式

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

样例

样例输入

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

样例输出

33

数据范围与提示