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