P3267 [JLOI2016/SHOI2016] Scout Wards

R and player B are playing a game. The game map consists of $N$ points and $N-1$ undirected edges, each connecting two points, and the map is connected. In other words, the map is a tree with $N$ nodes. There is an item called a scout ward. When a player places a scout ward at a point, it can monitor that point and all points whose distance from it is within $D$. The distance between two points is defined as their distance on the tree, i.e., the number of edges on the unique simple path between them. Placing a scout ward at a point has a certain cost, and the cost may differ between points. Now R knows all the positions where player B may appear. Please compute the minimum total cost to monitor all these positions.

The first line contains two positive integers $N$ and $D$, denoting the number of points on the map and the vision range of a scout ward, respectively. Points are numbered from $1$ to $N$. The second line contains $N$ positive integers. The $i$-th integer denotes the cost $W_i$ of placing a scout ward at point $i$. It is guaranteed that $W_i \le 1000$. The third line contains a positive integer $M$, denoting the number of points where player B may appear. It is guaranteed that $M \le N$. The fourth line contains $M$ positive integers, denoting the indices of the points where player B may appear, given in strictly increasing order without repetition. The next $N-1$ lines each contain two positive integers $U, V$, indicating that there is an undirected edge between points $U$ and $V$.

Output a single integer on one line, the minimum total cost required to monitor all points where player B may appear.

For all testdata, $N \le 5 \times 10^5$, $D \le 20$. Translated by ChatGPT 5