P1605 [NOI2016贵州省选] 侦察守卫
描述
小R和B神正在玩一款游戏。这款游戏的地图由n个点和m−1条无向边组成,每条无向边连接两个点,且地图是连通的。换句话说,游戏的地图是一 棵有n个节点的树。
游戏中有一种道具叫做侦查守卫,当一名玩家在一个点上放置侦查守卫后,它可以监视这个点以及与这个点的距离在d以内的所有点。这里两个点之间的距离定义为它们在树上的距离,也就是两个点之间唯一的简单路径上所经过边的条数。
在一个点上放置侦查守卫需要付出一定的代价,在不同点放置守卫的代价可能不同。现在小R知道了所有B神可能会出现的位置,请你计算监视所以这些位置的最小代价。
游戏中有一种道具叫做侦查守卫,当一名玩家在一个点上放置侦查守卫后,它可以监视这个点以及与这个点的距离在d以内的所有点。这里两个点之间的距离定义为它们在树上的距离,也就是两个点之间唯一的简单路径上所经过边的条数。
在一个点上放置侦查守卫需要付出一定的代价,在不同点放置守卫的代价可能不同。现在小R知道了所有B神可能会出现的位置,请你计算监视所以这些位置的最小代价。
输入
第一行包含两个正整数n和d,分别表示地图上的点数和侦查守卫的视野范围。约定地图上的点用1到n的整数编号。
第二行n个正整数,第i个正整数表示在编号为i的点放置侦查守卫的代价wi。保证wi≤1000。
第三行一个正整数m,表示B神可能出现的点的数量。保证m≤n。
第四行m个正整数,分别表示每个B神可能出现的点的编号,从小到大不重复地给出。
接下来n-1行,每行包含两个正整数u,v吗,表示在编号为u的点和编号为v的点之间有一条无向边。
第二行n个正整数,第i个正整数表示在编号为i的点放置侦查守卫的代价wi。保证wi≤1000。
第三行一个正整数m,表示B神可能出现的点的数量。保证m≤n。
第四行m个正整数,分别表示每个B神可能出现的点的编号,从小到大不重复地给出。
接下来n-1行,每行包含两个正整数u,v吗,表示在编号为u的点和编号为v的点之间有一条无向边。
输出
输出仅一行一个整数,表示监视所有B神可能出现的点所需要的最小代价。
样例输入
样例输出
提示
【样例说明】
分别在 4 号点和 9 号点上放置侦察守卫。
分别在 4 号点和 9 号点上放置侦察守卫。