这道题和小凸玩密室有点像,大概都是将小状态拼成大状态。

对于$x$,枚举$d$吧。

有$f_{x,i}$表示$x$的子树(含$x$)内所有关键点已经被覆盖,且可以向外延伸至少$i$距离。

对于每个$f_{x,i}$,怎么来?

对于当前处理到的子节点$y$,要覆盖当前子树$x$。

有两种情况,

第一种利用之前的$f_{x,i}+$$y$中还没有覆盖到的关键点

第二种利用当前的$f_{y,i+1}+$之前$x$中$f_{y,i+1}$没有触及到的关键点

因此需要设计多一个状态$g_{x,i}$表示当前$x$子树中距离大于等于$i$的关键点已经覆盖,小于$i$覆盖不覆盖无所谓的代价。

对于当前新添加的子树$y$,$f_{x,i}=\min\{f_{x,i}+g_{y,i},f_{y,i+1}+g_{x,i+1}\},g_{x,i}=\sum g_{y,i-1}$

还有无关当前状态的转移$f_{x,i}=\min\{f_{x,i},f_{x,i+1}\},g_{x,i}=\min\{g_{x,i},g_{x,i+1}\}$,这个是根据状态定义来的。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int mod=1e9+7,N=5e5+5;
const double pi=acos(-1);
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,next;}a[N<<1];int last[N],len;
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
int f[N][22],g[N][22],w[N],d;bool vis[N];
void dfs(int x,int fa)
{
    if(vis[x])f[x][0]=g[x][0]=w[x];
    else f[x][0]=g[x][0]=0;
    for(int i=1;i<=d;i++)f[x][i]=w[x];
    for(int k=last[x],y;k;k=a[k].next)
        if((y=a[k].y)!=fa)dfs(y,x);
    for(int k=last[x],y;k;k=a[k].next)
        if((y=a[k].y)!=fa)
        {
            for(int i=d;i>=0;i--)
                f[x][i]=min(f[x][i]+g[y][i],f[y][i+1]+g[x][i+1]);
            for(int i=d;i>=0;i--)
                f[x][i]=min(f[x][i],f[x][i+1]);
            g[x][0]=f[x][0];
            for(int i=1;i<=d+1;i++)
                g[x][i]+=g[y][i-1];
            for(int i=1;i<=d+1;i++)
                g[x][i]=min(g[x][i-1],g[x][i]);
        }
}
int main()
{
    len=0;memset(last,0,sizeof(last));
    int n;qr(n),qr(d);
    for(int i=1;i<=n;i++)qr(w[i]);
    int m;qr(m);
    for(int i=1,x;i<=m;i++)qr(x),vis[x]=1;
    for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
    memset(f,0x3f,sizeof(f));
    dfs(1,0);
    int ans=0x3f3f3f3f;
    for(int i=0;i<=d;i++)ans=min(ans,f[1][i]);
    qw(ans);puts("");
    return 0;
}