题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4557
树形DP。和“河流”有点像，也有一个类似“承诺”的东西。
就是用 f 表示当前节点向下 j 层之下的需覆盖点已覆盖的费用。答案可以是 f [ root ] [0] 。（root是随便一个点）
最好把当前节点看作第1层而不是第0层，这样就能用0表示当前节点的子树全覆盖了。
为了转移，引入一个 g ，表示当前点在自己子树全覆盖的基础上可以向外覆盖 j 层。这时当前节点可以自然地看作第0层了。
这也是为什么 f 表示的是“向下 j 层之下的点全覆盖”而不是“向下 j 层全覆盖”。就是为了方便转移。
没错，因为如果记成“向下 j 层全覆盖”，那么记录下“还有一些没覆盖”这一状态也根本没用，因为兄弟节点都是从上往下帮自己覆盖的；
而像这样记录成“向下还有 j 层没覆盖”，就有更多“把它们覆盖好”的机会，也方便转移等等，变得很顺畅！
具体转移的时候，发现 g 的转移依赖 f （上一次的 f 值），而 f 的转移不依赖 g ，所以要先求g的值。
可以用g[0]来更新 f [0] 的值，因为f [0] 是从当前节点的孩子们的 f 那里转移不过来的。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=5e5+,D=;const ll INF=0x7fffffff;
int n,m,d,head[N],xnt;
ll a[N],f[N][D],g[N][D];
bool need[N];
struct Edge{
int next,to;
Edge(int n=,int t=):next(n),to(t) {}
}edge[N<<];
void add(int a,int b)
{
edge[++xnt]=Edge(head[a],b);head[a]=xnt;
edge[++xnt]=Edge(head[b],a);head[b]=xnt;
}
void dfs(int cr,int fa)
{
f[cr][]=g[cr][]=need[cr]?a[cr]:;//只有根节点时的状态
for(int j=;j<=d;j++)g[cr][j]=a[cr];//初值
g[cr][d+]=INF;
for(int i=head[cr],v;i;i=edge[i].next)
{
if((v=edge[i].to)==fa)continue;
dfs(v,cr);
for(int j=;j<=d;j++)g[cr][j]=min(g[cr][j]+f[v][j],f[cr][j+]+g[v][j+]);//从0开始
for(int j=d;j;j--)g[cr][j-]=min(g[cr][j-],g[cr][j]);
f[cr][]=g[cr][]; //
for(int j=;j<=d;j++)f[cr][j]+=f[v][j-]; //这个不要放在28行之前，因为该行要用到上一次的值
for(int j=;j<=d;j++)f[cr][j]=min(f[cr][j],f[cr][j-]);
}
}
int main()
{
scanf("%d%d",&n,&d);for(int i=;i<=n;i++)scanf("%lld",&a[i]);
scanf("%d",&m);int tmp;for(int i=;i<=m;i++){scanf("%d",&tmp);need[tmp]=;}
int x,y;
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&y);add(x,y);
}
// memset(g,1,sizeof g);
dfs(,);
printf("%lld",f[][]);
return ;
}