样例下载

题目描述

一棵树含有 $n$ 个结点，编号为 $1$ ~ $n$。每个结点有一个属性值，编号为 $i$ 的点的属性值为 $W_i$。

现在要砍掉若干条边，把这棵树划分成若干棵子树，得到一个森林，要求森林中的每棵树包含的结点数量不少于 $a$，不大于 $b$。

定义一棵树的属性值为其包含的所有结点的属性值的平均值。

定义划分成森林的代价为森林包含的所有树的属性值的总和。

问：如何划分，可以使得划分的代价最小？

你只需要输出最小代价。如果不存在满足要求的划分方案，则输出 -1 。

输入格式

第一行：包含三个整数 $n, a, b$

第二行：包含 $n$ 个整数 $W_i$

接下来 $n − 1$ 行，每行两个整数 $u, v$ 表示点 $u$ 和点 $v$ 之间有一条树边。

输出格式

如果存在划分方案，则输出一个实数，表示划分的最小代价，四舍五入保留两位小数。否则输出 -1 。

输入样例

3 1 1
1 1 1
1 2
2 3

输出样例

3.00 

数据范围

100% 的数据，$1 ≤ a ≤ b ≤ n, 2 ≤ n ≤ 50, W_i ≤ 10^9$。