首先可以确定是树形DP，但这里存在跨子树的信息传递问题，这里就需要“借”的思想。
f[i][j]表示i子树内所有点都被覆盖到，且i以外j层内的点都能被覆盖到 的方案数。
g[i][j]表示i子树内离i距离不小于j的点都被覆盖到 的方案数。
这里f做了一个前缀和，g做了一个后缀和。
那么f有转移：
1.目前以x为根的子树还有点没被覆盖到，让新加的y子树内的守卫来覆盖。
f[x][j]=g[x][j+1]+f[k][j+1]
2.目前x子树以完全覆盖，那么允许y子树存在未覆盖的点。
f[x][j]=f[x][j]+g[k][j]
同理g有转移：g[x][j]+=g[y][j-1]
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 5 using namespace std; 6 7 const int N=500010,inf=1e9; 8 int n,m,x,u,v,d,tot,cnt,w[N],s[N],h[N],to[N<<1],nxt[N<<1],f[N][25],g[N][25]; 9 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } 10 11 void dfs(int x,int fa){ 12 rep(i,1,d) f[x][i]=w[x]; f[x][d+1]=inf; 13 if (s[x]) g[x][0]=f[x][0]=w[x]; 14 For(i,x) if ((k=to[i])!=fa){ 15 dfs(k,x); 16 rep(j,0,d) f[x][j]=min(f[x][j]+g[k][j],f[k][j+1]+g[x][j+1]); 17 for (int j=d; ~j; j--) f[x][j]=min(f[x][j],f[x][j+1]); 18 g[x][0]=f[x][0]; 19 rep(j,1,d) g[x][j]+=g[k][j-1]; 20 rep(j,1,d) g[x][j]=min(g[x][j],g[x][j-1]); 21 } 22 } 23 24 int main(){ 25 freopen("bzoj4557.in","r",stdin); 26 freopen("bzoj4557.out","w",stdout); 27 scanf("%d%d",&n,&d); 28 rep(i,1,n) scanf("%d",&w[i]); 29 scanf("%d",&m); 30 rep(i,1,m) scanf("%d",&x),s[x]=1; 31 rep(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u); 32 dfs(1,0); printf("%d ",g[1][0]); 33 return 0; 34 }