#P4557. [JLoi2016]侦察守卫
[JLoi2016]侦察守卫
[JLOI2016/SHOI2016] 侦察守卫
题目描述
小 R 和 B 神正在一张树形地图上玩游戏。小 R 可以在任意结点放置侦察守卫,在结点 放置一个守卫的代价是 。守卫可以监视它所在的结点,以及与它的距离不超过 的全部结点。距离按两点间唯一路径上的边数计算。
已给出 B 神可能出现的全部结点。请选择若干守卫的位置,使这些结点中的每一个都受到至少一个守卫监视,求最小总代价。
输入格式
第一行两个正整数 ,分别表示地图的结点数和守卫的监视距离。结点编号为 到 。
第二行 个正整数 ,表示各结点的放置费用。
第三行一个正整数 ,表示 B 神可能出现的结点数。
第四行 个严格递增的整数,表示这些结点的编号。
接下来 行,每行两个正整数 ,表示一条连接结点 的无向边。树的边读完后,末尾如有额外整数,不属于地图。
,,。
输出格式
输出一行一个整数,表示使全部指定结点受到监视的最小总代价。
样例
12 2
8 9 12 6 1 1 5 1 4 8 10 6
10
1 2 3 5 6 7 8 9 10 11
1 3
2 3
3 4
4 5
4 6
4 7
7 8
8 9
9 10
10 11
11 12
10