很显然是树形DP。
第一眼定义了f[u][i]表示向上覆盖i长度的最小代价。
但是因为这里的D是圈的影响范围，所以下面的点也会被该点影响到。显然不能这么简单处理。
我们再定义g[u][i]表示u点向下i层以下（包括i层）被覆盖的最小代价。这样中间空开的i长度也会得到处理。
这里我们可以思考一下转移：我们显然要边转移边更新。
假设当前到了u的某一棵子树v。
首先考虑f[u][i]的转移，因为我们需要满足所有的子树，显然转移关系是用+来进行。
可以得出下面的转移
f[u][i] = min(f[u][i]+g[v][i],g[u][i+1]+f[v][i+1]);
v->u的长度会被f的覆盖，因为u向上i，也代表着向下i。那么就表示f[u][i]我们一开始应该初始化为w[u]，表示放置了守卫，才能覆盖到。
后面，的就是v的i+1长度圈会覆盖。为什么从i+1开始，因为f[v][i+1]才能到f[u][i]。
对于g[u][i]只需要去加上f[v][i-1]即可。满足边走边转移
然后注意可能更长度的状态可以转移到当前所以对f，g做前缀最小值和后缀最小值的处理。
更多细节见代码。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 5e5+5; const int M = 12005; const LL Mod = 199999; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int n,D,w[N],f[N][25],g[N][25],vis[N]; vector<int> G[N]; /* f[u][i] - u的子树都覆盖完毕，还能向上覆盖i层的最小代价 g[u][i] - u的i层及以下子树都覆盖完毕的最小代价 f[u][i] = min(f[u][i]+g[v][i],g[u][i+1]+f[v][i+1]); f[u][i] = min(f[u][i],f[u][i+1]); g[u][0] = f[u][0]; g[u][i] = min(g[u][i],g[u][i-1]) */ void dfs(int u,int fa) { if(vis[u]) f[u][0] = g[u][0] = w[u]; else f[u][0] = g[u][0] = 0; for(rg int i = 1;i <= D;++i) f[u][i] = w[u]; f[u][D+1] = 0x3f; for(auto v : G[u]) { if(v == fa) continue; dfs(v,u); for(rg int i = 0;i <= D;++i) f[u][i] = min(f[u][i]+g[v][i],g[u][i+1]+f[v][i+1]); for(rg int i = D;i >= 0;--i) f[u][i] = min(f[u][i],f[u][i+1]); g[u][0] = f[u][0]; for(rg int i = 1;i <= D;++i) g[u][i] += g[v][i-1]; for(rg int i = 1;i <= D;++i) g[u][i] = min(g[u][i],g[u][i-1]); } } int main() { n = read(),D = read(); for(rg int i = 1;i <= n;++i) w[i] = read(); int m;m = read(); while(m--) { int x;x = read(); vis[x] = 1; } for(rg int i = 1;i < n;++i) { int u,v;u = read(),v = read(); G[u].push_back(v); G[v].push_back(u); } dfs(1,0); printf("%d ",f[1][0]); system("pause"); }