每日一题 [JLOI2016/SHOI2016]侦察守卫题解

这题是一个比较妙的DP题，我们并不能像处理普通的树形DP题那么做
我们发现我们一个点覆盖距离小于等于d的所有点，不仅仅是只涉及到祖先节点，还包括一条折线的情况，因此我们不是能很好的直接利用子树信息转移
我们在首先定义一个F的dp数组外还要定义一个G
我们定义F[x][i]代表x的子树还有i层没有完全被覆盖，G[x][i]代表x的子树全部覆盖完还能向上延伸i层
于是我们就可以利用F和G之间的关系来转移

G[x][j]=min(G[x][j]+F[to[i]][j],F[x][j+1]+G[to[i]][j+1]);

我们来看一下具体转移的式子
一种是利用x向上延伸的距离来覆盖to[i]，另外一种是用to[i]的延伸距离来覆盖x，这样就比较好理解了，F数组的转移就类似普通的树形DP更新子树信息就可以了
这题还需要注意的是我们要取个后缀min和max这样可以保证不会出现DP值不单调导致的错误
具体见代码吧！
代码：

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ------------------------- "<<endl
#define LL long long
#define DB double
#define pb push_back
inline LL read(){
    LL nm=0; bool fh=true; char cw=getchar();
    for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    return fh?nm:-nm;
}
#define M 500020
#define INF 1000000000
int tot,to[M<<1],nt[M<<1],fs[M];
int n,d,m,F[M][25],G[M][25],val[M];
bool vis[M];
inline void link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline void DP(int x,int last=0){
    if(vis[x]) F[x][0]=G[x][0]=val[x];
    for(int i=1;i<=d;i++) G[x][i]=val[x]; G[x][d+1]=INF;
    for(int i=fs[x];i;i=nt[i]) if(to[i]^last){
        DP(to[i],x);
        for(int j=d;~j;--j) G[x][j]=min(G[x][j]+F[to[i]][j],F[x][j+1]+G[to[i]][j+1]);
        for(int j=d;~j;--j) G[x][j]=min(G[x][j],G[x][j+1]);
        F[x][0]=G[x][0];
        for(int j=1;j<=d+1;j++) F[x][j]+=F[to[i]][j-1];
        for(int j=1;j<=d+1;j++) F[x][j]=min(F[x][j],F[x][j-1]);
    }
}
int main(){
    n=read(),d=read();
    for(int i=1;i<=n;i++) val[i]=read();
    m=read(); for(int i=1,x;i<=m;i++) x=read(),vis[x]=true;
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
    DP(1),printf("%d\n",G[1][0]);
    return 0;
}