bzoj 4557 侦察守卫

Posted on | Views:

树形 $dp$ .

  • 设 $f(i,j)$ 表示将子树 $i$ 内除了最上面 $j$ 层,其余关键点都被覆盖的最小代价.
  • $g(i,j)$ 表示子树 $i$ 内所有关键点都已被覆盖,并且还向上覆盖了 $j$ 层的最小代价.
  • 当前处理节点为 $u$ ,其中一个儿子节点为 $v$ ,有转移 $g(u,j)=\min(g(u,j)+f(v,j), f(u,j+1)+g(v,j+1)),f(u,j)=\sum f(v,j-1)$ .
  • 第一个转移表示让子树 $v$ 内的点来覆盖原来需要覆盖的 $j$ 层.第二个转移比较显然.
  • 最后再贪心考虑 $f,g$ 的前缀/后缀和,即 $f(u,j)\leftarrow f(u,j-1),g(u,j)\leftarrow g(u,j+1)$ . 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
void upd(int &x,int y)
{
	x=min(x,y);
}
const int inf=1e9;
const int MAXN=5e5+10;
int n,m,d,w[MAXN],flag[MAXN];
int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int f[MAXN][22],g[MAXN][22];
void dfs(int u,int fa)
{
	if(flag[u])
		f[u][0]=g[u][0]=w[u];
	for(int i=1;i<=d;++i)
		g[u][i]=w[u];
	g[u][d+1]=f[u][d+1]=inf;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa)
			continue;
		dfs(v,u);
		for(int j=0;j<=d;++j)
			g[u][j]=min(g[u][j]+f[v][j],f[u][j+1]+g[v][j+1]);
		for(int j=d-1;j>=0;--j)
			upd(g[u][j],g[u][j+1]);
		f[u][0]=g[u][0];
		for(int j=1;j<=d;++j)
			f[u][j]+=f[v][j-1];
		for(int j=1;j<=d;++j)
			upd(f[u][j],f[u][j-1]);
	}
}
int main()
{
	n=read(),d=read();
	for(int i=1;i<=n;++i)
		w[i]=read();
	m=read();
	for(int i=1;i<=m;++i)
		flag[read()]=1;
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	dfs(1,0);
	cout<<g[1][0]<<endl;
	return 0;
}