这题是一个比较妙的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; }