bzoj4557: [JLoi2016]侦察守卫 题意：给出一棵n(<=5e5)个点的树，可以选一些点放置守卫，覆盖与其距离不超过d(<=20)的所有点。每个点放置守卫有一定代价。给出m(<=n)个指定点，求所有指定点被覆盖的最小代价。
题解
我们感性地跑这样一个dp： · dp[i][d]表示以i为根的子树中，指定点被完全覆盖的最小代价。 · dp[i][d-j]表示子树中指定点被完全覆盖，同时能够覆盖i向上j层的最小代价。 · dp[i][d+j]表示i向下j层已经被覆盖后，剩下指定点被完全覆盖的最小代价。 怎么描述得这么乱呢 然后我们随便写一写转移就好啦！
复杂度O(nd)。
代码
#include<cstdio>
#define N 500001
#define inf 1e9
#define D 41
using namespace std;
int n,m,d,p,
sum,mn,f[N],c[N][D];
bool ned[N];
int to[N<<
1],hd[N<<
1],lk[N],cnt;
void add(
int u,
int v)
{to[++cnt]=v,hd[cnt]=lk[u],lk[u]=cnt;}
char ch;
void read(
int &x)
{
x=
0;
while(ch<
'0'|ch>
'9')ch=getchar();
while(ch>=
'0'&&ch<=
'9')
x=x*
10+ch-
'0',ch=getchar();
}
void dfs(
int x)
{
int v,i,j;
for(i=lk[x];i;i=hd[i])
if(f[x]!=to[i])
f[v=to[i]]=x,dfs(v),c[x][
0]+=c[v][d<<
1];
for(j=
1;j<=(d<<
1);j++)
{
c[x][j]=c[x][j-
1],mn=inf,
sum=
0;
for(i=lk[x];i;i=hd[i])
if(to[i]!=f[x])
{
v=to[i];
if(j>d)p=c[v][j-
1];
else
{
p=c[v][(d<<
1)-j];
if(mn>c[v][j-
1]-p)mn=c[v][j-
1]-p;
}
sum+=p;
}
if(c[x][j]>
sum+mn)c[x][j]=
sum+mn;
if(c[x][j]>
sum&&(j>d||j==d&&!ned[x]))c[x][j]=
sum;
}
}
int main()
{
read(n),read(d);
for(
int i=
1;i<=n;i++)
read(c[i][
0]);
read(m);
while(m--)
read(p),ned[p]=
1;
for(
int i=
1;i<n;i++)
read(m),read(p),
add(m,p),add(p,m);
dfs(f[
1]=
1);printf(
"%d",c[
1][d]);
}
题目无关
这道题曾为我带来深重的心理阴影。 插一段本来应属于【jloi2016游记】的东西 在下第一次 在比赛的某一天爆零 是JLOI2016的day1。多么令人怀念（大雾 当时感觉这道题好不可做啊，暴力调了1.5h没调出来，然后弃疗了。 后来查了题解，题解表示【这个dp很好理解】 但是当时在下非常弱，看不懂转移，因此受到了打击。
今天莫名想起来这道题，写了写，1A。（这只是因为以前见过题解…大约
