题解 P3267 【[JLOI2016]侦察守卫】
zcysky
2017-04-29 17:59:25
首先我认为**楼上的动态规划方程是错的**，状态不倒序存的话难道数量不会爆炸？
题意：每个点有一个覆盖半径，求覆盖完整棵树的最小代价。
定义状态：
$f[i][j]$ 表示在子树$i$ 中，向下还有深度$j$ 没有被覆盖的最小代价。
$g[i][j]$子树$i $已经被完全覆盖，向上已经覆盖了$j $层所需要的最小代价。
那么如果我们到了第$x $个节点，开始枚举第$u $个子树，我们需要的方程是：
$f[x][j]=min(min(f[x][j]+g[u][j],g[x][j+1]+f[u][j+1]),f[x][j-1])$
$g[x][0]=f[x][0]$
$g[x][i]=min(g[x][i-1],g[x][i]+g[u][i-1])$
所以代码如下：
```cpp
#include<bits/stdc++.h>
#define N 500005
#define inf 100000007
using namespace std;
struct Edge{int u,v,next;}G[N*2];
int n,m,d;
int val[N],head[N],f[N][25],g[N][25],tot=0;
bool vis[N];
inline void addedge(int u,int v){
G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot;
G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot;
}
void dfs(int u,int fa){
if(vis[u])f[u][0]=g[u][0]=val[u];
for(int i=1;i<=d;i++)g[u][i]=val[u];
g[u][d+1]=inf;
for(int i=head[u];i;i=G[i].next){
int v=G[i].v;if(v==fa)continue;
dfs(v,u);
for(int j=d;j>=0;j--)g[u][j]=min(g[u][j]+f[v][j],g[v][j+1]+f[u][j+1]);
for(int j=d;j>=0;j--)g[u][j]=min(g[u][j],g[u][j+1]);
f[u][0]=g[u][0];
for(int j=1;j<=d+1;j++)f[u][j]+=f[v][j-1];
for(int j=1;j<=d+1;j++)f[u][j]=min(f[u][j],f[u][j-1]);
}
}
inline int read(){
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
int main(){
freopen("observer.in","r",stdin);
freopen("observer.out","w",stdout);
n=read();d=read();
for(int i=1;i<=n;i++)val[i]=read();
m=read();int x;
for(int i=1;i<=m;i++){int x=read();vis[x]=true;}
for(int i=1;i<n;i++){
int u=read(),v=read();addedge(u,v);
}
dfs(1,0);
printf("%d\n",f[1][0]);
}
```