$ \color{#0066ff}{ 题目描述 }$
小 R 和 B 神正在玩一款游戏. 这款游戏的地图由 N 个点和 N-1 条无向边组成, 每条无向边连接两个点, 且地图是连通的. 换句话说, 游戏的地图是一棵有 N 个节点的树.
游戏中有一种道具叫做侦查守卫, 当一名玩家在一个点上放置侦查守卫后, 它可以监视这个点以及与这个点的距离在 D 以内的所有点. 这里两个点之间的距离定义为它们在树上的距离, 也就是两个点之间唯一的简单路径上所经过边的条数. 在一个点上放置侦查守卫需要付出一定的代价, 在不同点放置守卫的代价可能不同.
现在小 R 知道了所有 B 神可能会出现的位置, 请你计算监视所有这些位置的最小代价.
\(\color{#0066ff}{输入格式}\)
第一行包含两个正整数 N 和 D, 分别表示地图上的点数和侦查守卫的视野范围. 约定地图上的点用 1 到 N 的整数编号.
第二行 N 个正整数, 第 i 个正整数表示在编号为 i 的点放置侦查守卫的代价 Wi. 保证 Wi<=1000.
第三行一个正整数 M, 表示 B 神可能出现的点的数量. 保证 M<=N.
第四行 M 个正整数, 分别表示每个 B 神可能出现的点的编号, 从小到大不重复地给出.
接下来 N-1 行, 每行包含两个正整数 U,V, 表示在编号为 U 的点和编号为 V 的点之间有一条无向边.
\(\color{#0066ff}{输出格式}\)
仅一行一个整数, 表示监视所有 B 神可能出现的点所需要的最小代价
- \(\color{
- #0066ff
- }{
- 输入样例
- }\)
- 12 2
- 8 9 12 6 1 1 5 1 4 8 10 6
- 10
- 1 2 3 5 6 7 8 9 10 11
- 1 3
- 2 3
- 3 4
- 4 5
- 4 6
- 4 7
- 7 8
- 8 9
- 9 10
- 10 11
- 11 12
- \(\color{
- #0066ff
- }{
- 输出样例
- }\)
- 10
- \(\color{
- #0066ff
- }{
- 数据范围与提示
- }\)
对于所有的数据, N<=500000,D<=20
\(\color{#0066ff}{题解}\)
对于这种在树上覆盖的问题, 是一个比较经典的树形 DP 模型
状态 \(f[i][j]\) 表示以 i 为根子树从 i 向下有 j 层未覆盖的最小代价, j 可以为负数, 如果是负数, 就是子树全覆盖, 并向外覆盖一些层
所以我们再开一个 \(g[i][j]\) 表示以 i 为根子树全覆盖, 并且向外覆盖了 j 层的方案数
首先, 对于必覆盖点, 初始化就是 \(f[i][0]=g[i][0]=val[i]\)
注意当 \(j\ge 1\) 时, f 覆盖的范围是不包括当前点的 (j 层未覆盖), 但是 g 包括了 (i 向外 j 全覆盖)
所以 \(g[i][j]\) 也要初始化一下
考虑转移
对于 f, 显然有 \(f[x][j] = min\{f[x][j-1]\}\)
还有就是子树统计 \(f[x][j]+=f[y][j-1]\)
对于 g, 显然有 \(g[x][i]=min\{g[x][i+1]\}\)
还有, 就是考虑 x 的外面由哪个子树覆盖, 这个覆盖包括了 x 子树内部,\(g[y][j]\) 覆盖了 \(f[x][j]\) 未覆盖的 j 层
\(g[x][j]=min\{f[x][j+1]+g[y][j+1],f[y][j]+g[x][j]\}\)
答案就是 \(f[1][0]\)
- #include<bits/stdc++.h>
- #define LL long long
- LL in() {
- char ch; LL x = 0, f = 1;
- while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
- for(x = ch ^ 48; isdigit(ch = getchar()); x = (x <<1) + (x << 3) + (ch ^ 48));
- return x * f;
- }
- const int maxn = 5e5 + 100;
- const int inf = 0x7fffffff;
- int f[maxn][25], g[maxn][25], val[maxn];
- int n, d, m;
- bool vis[maxn];
- struct node {
- int to;
- node *nxt;
- node(int to = 0, node *nxt = NULL): to(to), nxt(nxt) {}
- };
- node *head[maxn];
- void add(int from, int to) { head[from] = new node(to, head[from]); }
- void dfs(int x, int fa) {
- if(vis[x]) f[x][0] = g[x][0] = val[x];
- for(int i = 1; i <= d; i++) g[x][i] = val[x];
- g[x][d + 1] = inf;
- for(node *i = head[x]; i; i = i->nxt) {
- if(i->to == fa) continue;
- dfs(i->to, x);
- for(int j = 0; j <= d; j++) g[x][j] = std::min(g[x][j] + f[i->to][j], g[i->to][j + 1] + f[x][j + 1]);
- for(int j = d - 1; j>= 0; j--) g[x][j] = std::min(g[x][j], g[x][j + 1]);
- f[x][0] = g[x][0];
- for(int j = 1; j <= d; j++) f[x][j] += f[i->to][j - 1];
- for(int j = 1; j <= d; j++) f[x][j] = std::min(f[x][j], f[x][j - 1]);
- }
- }
- int main() {
- n = in(), d = in();
- for(int i = 1; i <= n; i++) val[i] = in();
- m = in();
- for(int i = 1; i <= m; i++) vis[in()] = true;
- int x, y;
- for(int i = 1; i < n; i++) x = in(), y = in(), add(x, y), add(y, x);
- dfs(1, 0);
- printf("%d\n", f[1][0]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2998582.html