bzoj 4557: [JLoi2016]侦察守卫 树归

bzoj 4557: [JLoi2016]侦察守卫

设f[x][j]表示覆盖以x为根的子树的所有应该被覆盖的节点，并且以x为根的子树向下j层全部被覆盖的最小代价。

设g[x][j]表示与x距离大于j全部应该覆盖的节点全部被覆盖的最小代价。

有

f[u][j] = min{f[u][j]+g[v][j],g[u][j+1]+f[v][j+1],f[u][j+1]}

g[u][j] = min{g[u][j-1],g[u][j]+g[v][j-1]}

边界f[u][d+1] = inf;f[u][i] = c[u];(i <= d) f[u][0] = c[u] or  0

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

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 inline void read(int &x){

     x=;char ch;bool flag = false;

     while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

     while(x=*x+ch-'',ch=getchar(),ch>'!');if(flag) x=-x;

 }

 inline int cat_max(const ll &a,const ll &b){return a>b ? a:b;}

 inline int cat_min(const ll &a,const ll &b){return a<b ? a:b;}

 const int maxn = ;

 const int maxd = ;

 struct Edge{

     int to,next;

 }G[maxn<<];

 int head[maxn],cnt;

 void add(int u,int v){

     G[++cnt].to = v;

     G[cnt].next = head[u];

     head[u] = cnt;

 }

 ll f[maxn][maxd],g[maxn][maxd];

 int c[maxn],fa[maxn],d;

 bool h[maxn];

 #define v G[i].to

 void dfs(int u){

     if(h[u]) f[u][] = g[u][] = c[u];

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

     for(int i=;i<=d;++i) f[u][i] = c[u];

     f[u][d+] = 1000LL*maxn;

     for(int i = head[u];i;i=G[i].next){

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

         fa[v] = u;

         dfs(v);

         for(int j=d;j>=;--j){

             f[u][j] = cat_min(cat_min(f[u][j]+g[v][j],g[u][j+]+f[v][j+]),f[u][j+]);

         }

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

         for(int j=;j<=d+;++j){

             g[u][j] = cat_min(g[u][j-],g[u][j] + g[v][j-]);

         }

     }

 }

 #undef v

 int main(){

     int n;read(n);read(d);

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

     int m;read(m);

     for(int i=,x;i<=m;++i) read(x),h[x] = true;

     for(int i=,u,v;i<n;++i){

         read(u);read(v);

         add(u,v);add(v,u);

     }

     dfs();

     printf("%lld\n",g[][]);

     getchar();getchar();

     return ;

 }