题目：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+5,D=25;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=0,int t=0):next(n),to(t) {} }edge[N<<1]; 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][0]=g[cr][0]=need[cr]?a[cr]:0;//只有根节点时的状态 for(int j=1;j<=d;j++)g[cr][j]=a[cr];//初值 g[cr][d+1]=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=0;j<=d;j++)g[cr][j]=min(g[cr][j]+f[v][j],f[cr][j+1]+g[v][j+1]);//从0开始 for(int j=d;j;j--)g[cr][j-1]=min(g[cr][j-1],g[cr][j]); f[cr][0]=g[cr][0]; // for(int j=1;j<=d;j++)f[cr][j]+=f[v][j-1]; //这个不要放在28行之前，因为该行要用到上一次的值 for(int j=1;j<=d;j++)f[cr][j]=min(f[cr][j],f[cr][j-1]); } } int main() { scanf("%d%d",&n,&d);for(int i=1;i<=n;i++)scanf("%lld",&a[i]); scanf("%d",&m);int tmp;for(int i=1;i<=m;i++){scanf("%d",&tmp);need[tmp]=1;} int x,y; for(int i=1;i<n;i++) { scanf("%d%d",&x,&y);add(x,y); } // memset(g,1,sizeof g); dfs(1,0); printf("%lld",f[1][0]); return 0; }