Minimum Cost Coverage in a Tree

Two players, R and B, are playing a game on a map represented by a tree with N nodes and N-1 undirected edges. Each edge connects two nodes and the tree is connected.

In the game there is an item called a Spy Sentinel. When a player places a Spy Sentinel on a node, it monitors that node and every node within distance \(D\) from it. The distance between any two nodes is defined as the number of edges on the unique simple path between them.

Each node has a cost to place a Spy Sentinel, and these costs may differ among nodes. R knows all the potential positions where B might appear. Your task is to choose some nodes to place Spy Sentinels such that all these positions are monitored, and the total cost is minimized.

Note: All formulas are in \(\LaTeX\) format. For example, the tree has \(N\) nodes and \(N-1\) edges, and the distance condition is given by \(\text{distance} \le D\).

inputFormat

The input is given as follows:

• The first line contains three integers \(N\), \(D\), and \(M\), where \(N\) is the number of nodes in the tree, \(D\) is the monitoring distance, and \(M\) is the number of required nodes (B's possible positions).
• The second line contains \(N\) integers \(c_1, c_2, \ldots, c_N\), where \(c_i\) denotes the cost to place a Spy Sentinel at node \(i\).
• Each of the next \(N-1\) lines contains two integers \(u\) and \(v\), representing an undirected edge between node \(u\) and node \(v\).
• The last line contains \(M\) integers representing the nodes that need to be monitored.

It is guaranteed that the given edges form a tree.

outputFormat

Output a single integer — the minimum total cost required to monitor all the specified nodes. If it is impossible, output -1.

sample

3 1 2
3 2 1
1 2
2 3
1 3

2