记录编号	331137	评测结果	AAAAAAAAAA
题目名称	[JLOI&SHOI 2016] 侦察守卫	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	6.265 s
提交时间	2016-10-27 13:42:27	内存使用	83.10 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <cstdarg>
#include <vector>
#include <cmath>
using namespace std;
#define MAXN 500002
int n, m;
int d;
int w[MAXN];
bool app[MAXN]; //是否出现...
vector<int> G[MAXN];

int f[MAXN][22];
int g[MAXN][22];
void dp(int u, int p)
{
    if(app[u])f[u][0] = g[u][0] = w[u];  //这个应该放
    for(int i = 1; i <= d; i++)
        g[u][i] = w[u];    //这些位置都可能放
    g[u][d+1] = 0x3f3f3f3f; //这个覆盖不到
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];  //这是子节点...
        if(to == p)continue;
        dp(to, u);    
        for(int j = d; j >= 0; j--)
            g[u][j] = min(g[u][j]+f[to][j], g[to][j+1]+f[u][j+1]);
                            //这个很巧妙，能覆盖u点卫兵能监视到的范围...
        for(int j = d; j >= 0; j--)
            g[u][j] = min(g[u][j], g[u][j+1]); //按照g的定义更新g[u][j]
        f[u][0] = g[u][0]; //第二维0即，既不向上也不向下扩展
        for(int j = 1; j <= d+1; j++)
            f[u][j] += f[to][j-1];   //统计子节点的数据.
        for(int j = 1; j <= d+1; j++)
            f[u][j] = min(f[u][j-1], f[u][j]); //按照f的定义更新f
    }
}

int main()
{
    freopen("observer.in", "r", stdin);
    freopen("observer.out", "w", stdout);
    int __size__=128<<20;
    char *__p__=(char*)malloc(__size__)+__size__;
    __asm__("movl %0, %%esp\n"::"r"(__p__));
    //---- 开个栈防爆

    scanf("%d %d", &n, &d);
    for(int i = 1; i <= n; i++)
        scanf("%d", w+i);
    scanf("%d", &m);
    for(int i = 1; i <= m; i++)
    {
        int x;
        scanf("%d", &x);
        app[x] = true;
    }
    for(int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dp(1, 0);
    printf("%d\n", f[1][0]);
    return 0;
}