4557: [JLoi2016]侦察守卫

链接

分析：

　　因为D比较小，所设状态f[i][j]表示子树i内，从i往下第j层及第j层以下都覆盖了的最小代价，g[i][j]表示覆盖完子树内所有点，还可以往上覆盖j层的最小花费。

　　g的转移从子树内转移的时候，可以覆盖其他子树内的点， f数组直接求和即可。

　　最后要对g维护一下后缀最小值，对i维护前缀最小值。因为往上覆盖i+1的，一定可以更新往上覆盖i层的；往下有i层未覆盖的，一定可以更新往下有i-1层未覆盖的。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

struct Edge{ int to, nxt; } e[N << ];

int head[N], fa[N], En, D;

LL f[N][], g[N][], w[N];

bool ext[N];

inline void add_edge(int u,int v) {

    ++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En;

    ++En; e[En].to = u, e[En].nxt = head[v]; head[v] = En;

}

void dfs(int u) {

    if (ext[u]) f[u][] = g[u][] = w[u];

    for (int j = ; j <= D; ++j) g[u][j] = w[u];

    g[u][D + ] = 1e9;

    for (int i = head[u]; i; i = e[i].nxt) {

        int v = e[i].to;

        if (v == fa[u]) continue;

        fa[v] = u;

        dfs(v);

        for (int j = D; ~j; --j) g[u][j] = min(g[u][j] + f[v][j], g[v][j + ] + f[u][j + ]);

        for (int j = D; ~j; --j) g[u][j] = min(g[u][j], g[u][j + ]);

        f[u][] = g[u][];

        for (int j = ; j <= D + ; ++j) f[u][j] += f[v][j - ];

        for (int j = ; j <= D + ; ++j) f[u][j] = min(f[u][j], f[u][j  - ]);

    }

}

int main() {

    int n = read(); D = read();

    for (int i = ; i <= n; ++i) w[i] = read();

    int m = read();

    for (int i = ; i <= m; ++i) ext[read()] = ;

    for (int i = ; i < n; ++i) add_edge(read(), read());

    dfs();

    cout << f[][];

    return ;

}