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 ;
}
上一篇:Excel图表编辑---表格移动,样式修改


下一篇:ASP.NET MVC Controller激活系统详解2