分析
比较奥秘重重的 状态设计。定义 为覆盖以 为根的全部子树,而且向上覆盖了 层节点。 表示,覆盖了以 为根,子树节点深度 的全部节点。
初始化
- 对于任何情况 。选择这个节点的转移。
- 如果当前点是关键点,那么 。由于必须要覆盖这个节点,那么初始化为必选状态。
- 如果当前点不是关键点,那么 。对于非关键点可以不选。
转移
- 定义,不解释。
- ,当儿子转移到父亲,子树深度增加一。
- ,这个其实是滚动数组,只要我们正序枚举就可以了。
- 由于我们的转移只转移了端点,所以我们还要做一次前缀(后缀)最小值。
代码
#include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return f?-x:x; } const int N = 550000,inf = 1e9; int f[N][22],g[N][22],vis[N],val[N],n,m,d; struct Edge {int to,nxt;}e[N << 1]; int head[N],ecnt; void add(int x,int y) {e[++ecnt]=(Edge){y,head[x]};head[x]=ecnt;} void dfs(int x,int fa) { for(int i = 1;i <= d;i++) f[x][i] = val[x]; if(vis[x]) f[x][0] = val[x];f[x][d + 1] = inf; g[x][0] = f[x][0]; for(int i = head[x];i;i = e[i].nxt) { int y = e[i].to; if(y == fa) continue; dfs(y,x); for(int j = 0;j <= d;j++) f[x][j] = min(f[x][j] + g[y][j],f[y][j + 1] + g[x][j + 1]); for(int j = d;j >= 0;j--) f[x][j] = min(f[x][j],f[x][j + 1]); g[x][0] = f[x][0]; for(int j = 1;j <= d;j++) g[x][j] += g[y][j - 1]; for(int j = 1;j <= d;j++) g[x][j] = min(g[x][j],g[x][j - 1]); } } int main() { n = read();d = read(); for(int i = 1;i <= n;i++) val[i] = read(); m = read(); for(int i = 1,a;i <= m;i++) a = read(),vis[a] = 1; for(int i = 1;i < n;i++) { int x = read(),y = read(); add(x,y);add(y,x); } dfs(1,0); printf("%lld\n",f[1][0]); return 0; }