P3267 [JLOI2016/SHOI2016] 侦察守卫 题解
\(n\le 5\times10^5,D\le20\) 的数据范围显然想到 \(O(nd)\) 的树形 dp。考虑 \(d\) 这一维的状态设计。
考虑 \(i\) 子树中的情况分为全部被覆盖和未全部被覆盖两种。
- 对于第一种，显然我们要考虑子树中能 向上覆盖影响的点 的个数，于是设 \(f_{i,j}\) 表示 \(i\) 子树内最大能向上贡献 \(j\) 个点的最小值。
- 对于第二种，那么子树上方一定还会再放守卫，于是 当前子树之内的守卫等价于不会再做出贡献，只需要考虑最深的未被覆盖的点的深度。于是设 \(g_{i,j}\) 表示 \(i\) 子树内深度最深为 \(j\) 的点未被覆盖。
那么这个描述最值的状态定义是不好转移的，于是加上前缀最小值的限制就好转移了。依次枚举 \(x\) 的每个子节点 \(y\) 转移，转移完再前缀最小值。
方程容易列出：
\[f_{x,j}=\min(f_{x,j}+g_{y,j},f_{y,j+1}+g_{x,j+1}) \]\[g_{x,y}\leftarrow g_{y,j-1} \]含义是分别考虑做 \(j\) 贡献是 \(y\) 还是 \(y\) 以前的子节点。
本题的关键是能够清晰分类，并且想到按照情况确定 \(d\) 这一维不同的状态设计。
代码：
#include <bits/stdc++.h>
#define N 500005
#define M 22
using namespace std;
int n, d;
int m;
struct Node {
int to, nxt;
} e[N << 1];
int head[N], cnt;
void add(int u, int v) {
e[++cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int val[N];
int f[N][M], g[N][M];
int flg[N];
void dfs(int x, int fa) {
for (int i = 1; i <= d; i++)
f[x][i] = val[x];
if (flg[x])
f[x][0] = g[x][0] = val[x];
f[x][d + 1] = 0x3f3f3f3f;
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; 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], g[x][j] = min(g[x][j], g[x][j - 1]);
}
}
int main() {
cin >> n >> d;
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]);
cin >> m;
while (m--) {
int x;
scanf("%d", &x);
flg[x] = 1;
}
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
cout << f[1][0] << "\n";
return 0;
}