解题：JLOI 2016 侦查守卫

题面

经典的$cov-unc$树形dp(这词是你自己造的吧=。=)

设$cov[i][j]$表示覆盖完$i$的子树后至少向外再覆盖$j$层的最小代价，$unc[i][j]$表示$i$的子树中还剩下至少$j$层没有覆盖时的最小代价，然后是两个数组的抵消转移什么的

1.边界：对于每个需要覆盖的节点$i$，$unc[i][0]=cov[i][0]=cost_i$，对于不需要覆盖的节点$unc[i][0]=cov[i][0]=0$

而对于每个点$i$，又都有$unc[i][j]=0,cov[i][j]=cost_i(j∈N^*\&\&j<=d)$

2.$cov$的转移

对于每个距离$j$，显然有$cov[i][j]+=unc[goal[i]][j]$(覆盖它当前这个子树)

然后对于距离小于$d$的情况有$cov[i][j]=min(cov[i][j],unc[i][j+1]+cov[goal[i]][j+1])$(子树向外覆盖)

还有我们定义的是“至少”：$cov[i][j]=min(cov[i][j],cov[i][j+1])$

3.$unc$的转移

显然的，有$unc[i][0]=cov[i][0]$

子树的第$i-1$层被覆盖则自己的第$i$层被覆盖，同时也是注意定义里的“最少”：$unc[i][j]=min(unc[i][j]+unc[goal[i]][j-1],unc[i][j-1]$

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,K=;

 int p[N],noww[*N],goal[*N];

 int cst[N],imp[N],unc[N][K],cov[N][K];

 int n,d,m,t1,t2,cnt,ans=0x3f3f3f3f;

 void link(int f,int t)

 {

     noww[++cnt]=p[f];

     goal[cnt]=t,p[f]=cnt;

 }

 void DFS(int nde,int fth)

 {

     if(imp[nde]) unc[nde][]=cov[nde][]=cst[nde];

     for(int i=;i<=d;i++) cov[nde][i]=cst[nde];

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             DFS(goal[i],nde);

             for(int j=d;~j;j--)

             {

                 cov[nde][j]+=unc[goal[i]][j];

                 if(j<d)

                 {

                     cov[nde][j]=min(cov[nde][j],cov[nde][j+]);

                     cov[nde][j]=min(cov[nde][j],cov[goal[i]][j+]+unc[nde][j+]);

                 }

             }

             unc[nde][]=cov[nde][];

             for(int j=;j<=d;j++)

                 unc[nde][j]=min(unc[nde][j]+unc[goal[i]][j-],unc[nde][j-]);

         }

 }

 int main ()

 {

     scanf("%d%d",&n,&d);

     for(int i=;i<=n;i++)

         scanf("%d",&cst[i]);

     scanf("%d",&m);

     for(int i=;i<=m;i++)

         scanf("%d",&t1),imp[t1]=true;

     for(int i=;i<n;i++)

     {

         scanf("%d%d",&t1,&t2);

         link(t1,t2),link(t2,t1);

     }

     DFS(,);

     for(int i=;i<=d;i++)

         ans=min(ans,cov[][i]);

     printf("%d",ans);

     return ;

 }