令g[i][j]表示覆盖了i的子树中距离i大于等于j的所有点,f[i][j]表示覆盖了i的子树和子树外距离i小于等于j的所有点,有递推式$f[i][j]=min(f[i][j]+g[son][j],f[son][j+1]+g[i][j+1]),g[i][j]+=g[son][j-1]$,特别的有g[i][0]=f[i][0]

 1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 500005
4 struct ji{
5 int nex,to;
6 }edge[N<<1];
7 int E,n,d,x,y,w[N],vis[N],head[N],f[N][31],g[N][31];
8 void add(int x,int y){
9 edge[E].nex=head[x];
10 edge[E].to=y;
11 head[x]=E++;
12 }
13 void dfs(int k,int fa){
14 if (vis[k])f[k][0]=g[k][0]=w[k];
15 for(int i=1;i<=d;i++)f[k][i]=w[k];
16 f[k][d+1]=0x3f3f3f3f;
17 for(int i=head[k];i!=-1;i=edge[i].nex)
18 if (edge[i].to!=fa){
19 int v=edge[i].to;
20 dfs(v,k);
21 for(int j=0;j<=d;j++)f[k][j]=min(f[k][j]+g[v][j],f[v][j+1]+g[k][j+1]);
22 for(int j=d;j>=0;j--)f[k][j]=min(f[k][j],f[k][j+1]);
23 g[k][0]=f[k][0];
24 for(int j=1;j<=d;j++)g[k][j]+=g[v][j-1];
25 for(int j=1;j<=d;j++)g[k][j]=min(g[k][j],g[k][j-1]);
26 }
27 }
28 int main(){
29 scanf("%d%d",&n,&d);
30 for(int i=1;i<=n;i++)scanf("%d",&w[i]);
31 scanf("%d",&x);
32 for(int i=1;i<=x;i++){
33 scanf("%d",&y);
34 vis[y]=1;
35 }
36 memset(head,-1,sizeof(head));
37 for(int i=1;i<n;i++){
38 scanf("%d%d",&x,&y);
39 add(x,y);
40 add(y,x);
41 }
42 dfs(1,0);
43 printf("%d",f[1][0]);
44 }

最新文章

  1. 移动到web整理
  2. gdb注意事项
  3. 《Linux内核设计与实现》CHAPTER5阅读梳理
  4. MySql、SqlServer、Oracle 三种数据库查询分页方式
  5. 原生js基础问题的一些备忘
  6. win7 摄像头驱动软件找不到,只有sys文件
  7. LeetCode Minimum Path Sum (简单DP)
  8. 也谈SWD接口协议分析
  9. php获取上传多个文件缺失
  10. FTP服务详解
  11. K最近邻算法
  12. PHPExcel融入ZF2
  13. NYOJ 128 前缀表达式的计算
  14. Gradle、Gradle Wrapper与Android Plugin for Gradle
  15. linux 出错 “INFO: task xxxxxx: 634 blocked for more than 120 seconds.”的3种解决方案
  16. 剑指offer(27)字符串的排列
  17. easyui datagrid编辑
  18. Ruby知识点三:运算符
  19. Linux运维二:CentOS6.6系统安装后的基本配置与优化
  20. ZOJ 2112 Dynamic Rankings (动态第k大,树状数组套主席树)

热门文章

  1. Windows下的程序及热键监视神器——Spy++
  2. iframe、SameSite与CEF
  3. 双指针之滑动窗口(长度最小的子数组 和 和为s的连续正数序列)
  4. modal框
  5. 双系统升win11(grub启动问题修复与讲解)?!?
  6. Proxychains完成Linux命令行代理
  7. javascript-jquery插件
  8. 【UE4 调试】提升UE4源码版本Setup下载速度
  9. dfs初步模板解析
  10. K8S_Kubernetes