因为在某个点见检查点还有自己的代价，而不是代价都是1，所以就不能用贪心做了。
所以这道题是神奇的树形dp。
树形dp一般自下向上，所以我们定义dp[i][j]为已经处理了以i为根的子树，还可以往上覆盖j层的最小代价。
直接转移很困难，可能出现子树间相互覆盖的情况。
覆盖还可以向下，于是定义了f[i][j]表示以i为根的子树向下j层（i自己也算是一层）没有覆盖的最小代价。
反正我觉得这个定义挺迷的，应该是我太弱了。
转移方程在代码里，写有注释。
#include<bits/stdc++.h> #define LL long long #define N 500003 #define INF 2100000000 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } struct EDGE{ int nextt,to; }w[N*2]; int head[N],tot=0; int cost[N],B[N]; int dp[N][22];//以x为根的子树已经处理好，还可以至少再往上覆盖j层的最小代价(可以向上覆盖) int f[N][22];//以x为根往下j层（x自己也算一层）没有被覆盖的最小代价(下面需要覆盖) int n,D,m; void add(int a,int b) { tot++; w[tot].nextt=head[a]; w[tot].to=b; head[a]=tot; } void dfs(int x,int fa) { if(B[x])f[x][0]=dp[x][0]=cost[x];//x作为检查点 for(int i=1;i<=D;++i)dp[x][i]=cost[x]; dp[x][D+1]=INF; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(v==fa)continue; dfs(v,x);//一个一个子树的合并处理 for(int j=D;j>=0;--j)dp[x][j]=min(dp[x][j]+f[v][j],dp[v][j+1]+f[x][j+1]); //用前几个儿子已经得出的dp[x][j]去覆盖v 或者用v覆盖u for(int j=D;j>=0;--j)dp[x][j]=min(dp[x][j],dp[x][j+1]); f[x][0]=dp[x][0]; for(int j=1;j<=D+1;++j)f[x][j]+=f[v][j-1]; for(int j=1;j<=D+1;++j)f[x][j]=min(f[x][j],f[x][j-1]); //对于f，可能距离小的比大的还优，所以还要再求一遍前缀最小值 //同理对于dp，可能覆盖距离大的比距离小的还优 } } int main() { n=read();D=read(); for(int i=1;i<=n;++i)cost[i]=read(); m=read(); for(int i=1;i<=m;++i)B[read()]=1; for(int i=1;i<n;++i) { int a=read(),b=read(); add(a,b);add(b,a); } dfs(1,1); printf("%d\n",f[1][0]); } /* 5 2 2 1 5 3 4 */
原文：https://www.cnblogs.com/yyys-/p/11722364.html
