BZPRO
#4711. 小奇挖矿
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
【题目背景】
小奇在喵星系使用了无限非概率驱动的采矿机，以至于在所有星球上都采出了一些矿石，现在它准备建一些矿石仓
库并把矿石运到各个仓库里。
【问题描述】
喵星系有n个星球，标号为1到n，星球以及星球间的航线形成一棵树。所有星球间的双向航线的长度都为1。小奇要
在若干个星球建矿石仓库，设立每个仓库的费用为K。对于未设立矿石仓库的星球，设其到一个仓库的距离为i，则
将矿石运回的费用为Di。请你帮它决策最小化费用。
输入格式
第一行2个整数n，K。
第二行n-1个整数，D1,D2,…Dn-1,保证Di<=Di+1。
接下来n-1行，每行2个整数x，y，表示星球x和星球y存在双向航线。
n<=200，0<=K，Di<=100000
输出格式
输出一行一个整数，表示最小费用。
样例
样例输入
8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5
样例输出
38
【样例解释】
在1，2号星球建立仓库。
数据范围与提示
BZPRO