#P4557. [JLoi2016]侦察守卫

    ID: 2881 传统题 2000ms 256MiB 尝试: 730 已通过: 382 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划树形 DP排序与序列处理前后缀最值CF2500三分

[JLoi2016]侦察守卫

[JLOI2016/SHOI2016] 侦察守卫

题目描述

小 R 和 B 神正在一张树形地图上玩游戏。小 R 可以在任意结点放置侦察守卫,在结点 ii 放置一个守卫的代价是 wiw_i。守卫可以监视它所在的结点,以及与它的距离不超过 dd 的全部结点。距离按两点间唯一路径上的边数计算。

已给出 B 神可能出现的全部结点。请选择若干守卫的位置,使这些结点中的每一个都受到至少一个守卫监视,求最小总代价。

输入格式

第一行两个正整数 n,dn,d,分别表示地图的结点数和守卫的监视距离。结点编号为 11 到 nn。

第二行 nn 个正整数 w1,…,wnw_1,\ldots,w_n,表示各结点的放置费用。

第三行一个正整数 mm,表示 B 神可能出现的结点数。

第四行 mm 个严格递增的整数,表示这些结点的编号。

接下来 n−1n-1 行,每行两个正整数 u,vu,v,表示一条连接结点 u,vu,v 的无向边。树的边读完后,末尾如有额外整数,不属于地图。

1≤m≤n≤5×1051\le m\le n\le5\times10^5,1≤d≤201\le d\le20,1≤wi≤10001\le w_i\le1000。

输出格式

输出一行一个整数,表示使全部指定结点受到监视的最小总代价。

样例

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