Solution -「洛谷 P3267」「JLOI 2016」「SHOI 2016」侦察守卫

Description

Link.

给你一棵树，放置守卫在某个点上面需要一定代价和一定的有效范围。让你覆盖若干指定点，求最小代价

Solution

算法标签：

$\ \ \ \ \ \ \ \ \ $ 树DP

DP状态定义:

$\ \ \ \ \ \ \ \ \ $ 说实话这道题定状态不好定。

$\ \ \ \ \ \ \ \ \ $ 那么我们从头来看，当 $d =0$ 的时候，我们就是在求树的最大独立集，定义显而易见。

$\ \ \ \ \ \ \ \ \ $ $d\neq 0$ 我们可以照搬原来的定义，把它扩展一下。

$\ \ \ \ \ \ \ \ \ $ $f_{i,j}$ 表示以 $i$ 为根结点的子树已经完全被覆盖让然后还能向上覆盖 $j$ 层的最小代价

$\ \ \ \ \ \ \ \ \ $ $g_{i,j}=$ 表示以 $i$ 为根结点的子树还有 $j$ 层没有覆盖的最小代价

$\ \ \ \ \ \ \ \ \ $ 需要注意的是 $j$ 本质上是带有方向性的，可以类比向量的概念。

$\ \ \ \ \ \ \ \ \ $ 边界条件很显然，$f_{i,0}=val_{i}$ 此时当前结点需要被覆盖。

$\ \ \ \ \ \ \ \ \ $ 其他情况：

$$ \begin{cases} f_{i,j}=val_{i},j\in [1,d] \\ \displaystyle f_{i,j}=\infty,j=d+1 \end{cases} $$

$\ \ \ \ \ \ \ \ \ $ 状态转移方程倒是比较好想，这里就不再赘述。

#include <cstdio>
#include <algorithm>
#include <queue>

char buf[1 << 21], *p1 = buf, *p2 = buf;
#ifndef ONLINE_JUDGE
#define gc() getchar()
#else
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#endif
#define is_number (ch >= '0' && ch <= '9')

template < typename Type >
void read(Type& a) {
    a = 0; bool f = 0; char ch;
    while (!(ch = gc(), is_number)) if (ch == '-') f = 1;
    while (is_number) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = gc();
    a = (f ? -a : a);
}

template < typename Type, typename... Args >
void read(Type& t, Args&... args) {
    read(t), read(args...);
}

int val[500005], f[500005][25];
int g[500005][25], vis[500005];
int n, m, d, tot, head[500005];
int nxt[1000005], to[1000005];
std::vector < std::vector < int > > G(500005);

void add(int x, int y) {
    to[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
    G[x].push_back(y);
    G[y].push_back(x);
}

void DP(int x, int fa) {
    if (vis[x]) g[x][0] = f[x][0] = val[x];
    for (int i = 1; i <= d; ++i) f[x][i] = val[x];
    f[x][d + 1] = 0x3f3f3f3f;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y ^ fa) {
            DP(y, x);
            for (int j = d; j >= 0; --j)
                f[x][j] = std::min(f[y][j + 1] + g[x][j + 1], f[x][j] + g[y][j]);
            for (int j = d; j >= 0; --j)
                f[x][j] = std::min(f[x][j + 1], f[x][j]);
            g[x][0] = f[x][0];
            for (int j = 1; j <= d + 1; ++j)
                g[x][j] += g[y][j - 1];
            for (int j = 1; j <= d + 1; ++j)
                g[x][j] = std::min(g[x][j - 1], g[x][j]);
        }
    }
}

signed main() {
    read(n, d);
    for (int i = 1; i <= n; ++i) read(val[i]);
    read(m);
    for (int i = 0, x; i < m; ++i) read(x), vis[x] = 1;
    for (int i = 1, x, y; i < n; ++i) read(x, y), add(x, y), add(y, x);
    DP(1, 0);
    printf("%d\n", g[1][0]);
}