题目链接
题解
orz
比较难的树形dp
不过想想也还好
看数据猜状态，一维是点，一维是D
那么就先设(f[i][j])表示(i)所在子树已处理完毕，还能向上【或向任意方向】覆盖(j)层的最小代价
考虑转移，会发现子树间会相互影响，一个子树用(f[s][j + 1])更新了(f[i][j])，其它的子树就完全没必要再用(f[s'][j + 1])去更新了，此时反而可以用(f[i][j])来减少该子树付出的代价
所以我们设一个(g[i][j])表示(i)为根的子树前(j)层待覆盖，(j)层以下已处理完毕的最小代价
(f[i][j])包含(f[i][j - 1])，所以我们可以设状态(f[i][j])中(j)表示小于等于(j)
同样设(g[i][j])中的(j)表示大于等于(j)
状态转移：枚举子树(s)
[f[i][j] = min{f[i][j] + g[s][j],f[s][j + 1] + g[i][j + 1]}
]
[g[i][j] += g[s][j - 1]
]
初始化就考虑(i)号点是不是一定被覆盖，就可以确定(f[i][0])和(g[i][0])的初值
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 500005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int h[maxn],ne = 2;
struct EDGE{int to,nxt;}ed[maxn << 1];
inline void build(int u,int v){
ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;
ed[ne] = (EDGE){u,h[v]}; h[v] = ne++;
}
int n,m,D,f[maxn][23],g[maxn][23],val[maxn],dan[maxn],fa[maxn];
int son[maxn],si;
void dfs(int u){
for (int i = 1; i <= D; i++) f[u][i] = val[u];
if (dan[u]) f[u][0] = g[u][0] = val[u];
f[u][D + 1] = INF;
Redge(u) if ((to = ed[k].to) != fa[u]){
fa[to] = u; dfs(to);
for (int i = 0; i <= D; i++)
f[u][i] = min(f[u][i] + g[to][i],f[to][i + 1] + g[u][i + 1]);
for (int i = D; i >= 0; i--)
f[u][i] = min(f[u][i],f[u][i + 1]);
g[u][0] = f[u][0];
for (int i = 1; i <= D; i++)
g[u][i] += g[to][i - 1];
for (int i = 1; i <= D; i++)
g[u][i] = min(g[u][i],g[u][i - 1]);
}
}
int main(){
n = read(); D = read();
REP(i,n) val[i] = read();
m = read();
REP(i,m) dan[read()] = true;
for (int i = 1; i < n; i++) build(read(),read());
dfs(1);
printf("%d
",f[1][0]);
return 0;
}