分析

比较奥秘重重的 状态设计。定义 为覆盖以 为根的全部子树，而且向上覆盖了 层节点。 表示，覆盖了以 为根，子树节点深度 的全部节点。

• 初始化

  • 对于任何情况 。选择这个节点的转移。
  • 如果当前点是关键点，那么 。由于必须要覆盖这个节点，那么初始化为必选状态。
  • 如果当前点不是关键点，那么 。对于非关键点可以不选。

• 转移

  • 定义，不解释。
  • ，当儿子转移到父亲，子树深度增加一。
  • ，这个其实是滚动数组，只要我们正序枚举就可以了。
  • 由于我们的转移只转移了端点，所以我们还要做一次前缀（后缀）最小值。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
const int N = 550000,inf = 1e9;
int f[N][22],g[N][22],vis[N],val[N],n,m,d;
struct Edge {int to,nxt;}e[N << 1];
int head[N],ecnt;
void add(int x,int y) {e[++ecnt]=(Edge){y,head[x]};head[x]=ecnt;}
void dfs(int x,int fa) {
    for(int i = 1;i <= d;i++) f[x][i] = val[x];
    if(vis[x]) f[x][0] = val[x];f[x][d + 1] = inf;
    g[x][0] = f[x][0];
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;
        if(y == fa) continue;
        dfs(y,x);
        for(int j = 0;j <= d;j++) f[x][j] = min(f[x][j] + g[y][j],f[y][j + 1] + g[x][j + 1]);
        for(int j = d;j >= 0;j--) f[x][j] = min(f[x][j],f[x][j + 1]);
        g[x][0] = f[x][0];
        for(int j = 1;j <= d;j++) g[x][j] += g[y][j - 1];
        for(int j = 1;j <= d;j++) g[x][j] = min(g[x][j],g[x][j - 1]);
    }
}
int main() {
    n = read();d = read();
    for(int i = 1;i <= n;i++) val[i] = read();
    m = read();
    for(int i = 1,a;i <= m;i++) a = read(),vis[a] = 1;
    for(int i = 1;i < n;i++) {
        int x = read(),y = read();
        add(x,y);add(y,x);
    }
    dfs(1,0);
    printf("%lld\n",f[1][0]); 
    return 0;
}