本文共 3340 字，大约阅读时间需要 11 分钟。

为了解决这个问题，我们需要找到一种方法来放置侦查守卫，使得所有B神可能出现的位置都被监视，同时代价最小。我们可以利用树的结构和动态规划来高效地解决这个问题。

方法思路

解决代码

import sys
from collections import deque
def main():
    sys.setrecursionlimit(1 << 25)
    n, d = map(int, sys.stdin.readline().split())
    w = list(map(int, sys.stdin.readline().split()))
    m = int(sys.stdin.readline())
    targets = list(map(int, sys.stdin.readline().split()))
    edges = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, sys.stdin.readline().split())
        edges[u].append(v)
        edges[v].append(u)
    
    visited = [False] * (n + 1)
    parent = [0] * (n + 1)
    children = [[] for _ in range(n + 1)]
    q = deque()
    q.append(1)
    visited[1] = True
    while q:
        u = q.popleft()
        for v in edges[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                children[u].append(v)
                q.append(v)
    
    target_set = set(targets)
    
    f = [[0] * (d + 1) for _ in range(n + 1)]
    g = [[0] * (d + 1) for _ in range(n + 1)]
    
    stack = []
    visited_dp = [False] * (n + 1)
    stack.append((1, 0))
    while stack:
        node, depth = stack.pop()
        if visited_dp[node]:
            continue
        visited_dp[node] = True
        for child in children[node]:
            stack.append((child, depth + 1))
    
    post_order = []
    stack = [(1, False)]
    while stack:
        node, processed = stack.pop()
        if processed:
            post_order.append(node)
            continue
        stack.append((node, True))
        for child in children[node]:
            stack.append((child, False))
    
    for u in post_order:
        f[u][0] = w[u]
        g[u][0] = 1
        for k in range(1, d + 1):
            f[u][k] = float('inf')
            g[u][k] = float('inf')
        for child in children[u]:
            for k in range(d + 1):
                if f[child][k] == float('inf'):
                    continue
                if f[u][k] > f[child][k] + w[u]:
                    f[u][k] = f[child][k] + w[u]
                    g[u][k] = g[child][k] + 1
                if g[u][k] > g[child][k] + 1:
                    g[u][k] = g[child][k] + 1
            for k in range(d, 0, -1):
                if f[u][k] > f[u][k-1]:
                    f[u][k] = f[u][k-1]
                if g[u][k] > g[u][k-1]:
                    g[u][k] = g[u][k-1]
        for k in range(1, d + 1):
            f[u][k] = min(f[u][k], f[u][k-1])
            g[u][k] = min(g[u][k], g[u][k-1])
        f[u][0] = min(f[u][0], f[u][1])
        g[u][0] = min(g[u][0], g[u][1])
    
    res = float('inf')
    for t in targets:
        for k in range(d + 1):
            if g[1][k] >= n:
                res = min(res, f[1][k])
    print(res)
if __name__ == "__main__":
    main()

代码解释

通过这种方法，我们能够高效地解决这个问题，确保所有B神可能出现的位置都被覆盖，同时代价最小。