8711: BZOJ4711:小奇挖矿
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
【题目背景】 小奇在喵星系使用了无限非概率驱动的采矿机,以至于在所有星球上都采出了一些矿石,现在它准备建一些矿石仓 库并把矿石运到各个仓库里。 【问题描述】 喵星系有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号星球建立仓库。
提示
没有写明提示
题目来源
没有写明来源