bzoj 4893 聚变反应炉

Posted on | Views:

贪心 + 树形背包.

  • 本以为此题必有高论,但发现只有 $n-1$ 条边,是个树.那很显然就是一个树形背包了.

前 $50$ 分 $n$ 比较大,但 $c_i\in \lbrace 0,1 \rbrace$ ,可以贪心.
显然先将所有 $c=1$ 的点激发,再激发 $c=0$ 的点最优,

  • 对于后面的 $50$ 分, $n\leq 2000$ ,树形背包解决.
  • 设 $f(u,x)$ 表示将子树 $u$ 内的点全部激发,并且节点 $u$ 初始需要 $x$ 点能量激发.
  • $dfs$ 到节点 $u$ 时,枚举它的所有儿子 $v$ ,递归下去计算出所有 $v$ 的 $f$ 值.
  • 先选一些儿子出来(选 $0$ 个也可),将它们的子树激发,再激发 $u$ ,再激发剩余的子树.那么一个儿子 $v$ 被选,造成的贡献是 $f(v,d_v)$ ,没被选,造成的贡献是 $f(v,\max(d_v-c_u,0))$ , $u$ 的贡献是 $x$ 减去选了的 $c_v$ ,与 $0$ 取 $\max$ .
  • 设 $g(i,j)$ 表示考虑了前 $i$ 个儿子,选了的儿子 $c_v$ 总和是 $j$ 时,前 $i$ 个儿子造成的最小贡献.
  • 对于第 $i$ 个儿子 $v$ ,若选它,有转移 $g(i,j+c_v)\leftarrow g(i-1,j)+f(v,d_v)$ .
  • 若不选它,有转移 $g(i,j)\leftarrow g(i-1,j)+f(v,\max(d_v-c_u,0))$ .
  • 若 $u$ 有 $k$ 个儿子,那么 $f(u,x)=\min \lbrace g(k,j)+\max(x-j,0)\rbrace$ .
  • 注意到 $f$ 的第二维 $x$ 对于确定的 $u$ ,其实只有 $2$ 种取值 $\lbrace d_u,\max(d_u-c_{fa},0)\rbrace$ ,分别用 $0,1$ 代替即可.
  • 时间复杂度 $O(n\cdot \sum c_i)$ .
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#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=1e5+10,MAXS=1e4+10;
int n,c[MAXN],d[MAXN],fa[MAXN];
int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
int sumc[MAXN];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int f[2019][2],g[2019][MAXS];
int calc(int u,int x)
{
	if(!x)
		return d[u];
	if(x==1)
		return max(0,d[u]-c[fa[u]]);
}
void solve(int u,int id,int k)
{
	int x=calc(u,id);
	if(!k)
	{
		f[u][id]=x;
		return;
	}
	int i=0;
	for(int I=head[u];I;I=nx[I])
	{
		int v=to[I];
		if(v==fa[u])
			continue;
		++i;
		for(int j=0;j<=sumc[u];++j)
		{
			if(j+c[v]<=sumc[u])
				upd(g[i][j+c[v]],g[i-1][j]+f[v][0]);
			upd(g[i][j],g[i-1][j]+f[v][1]);
		}
	}
	f[u][id]=inf;
	for(int j=0;j<=sumc[u];++j)
		f[u][id]=min(f[u][id],g[k][j]+max(x-j,0));
	for(int i=1;i<=k;++i)
		for(int j=0;j<=sumc[u];++j)
			g[i][j]=inf;
}
void dfs(int u,int Fa)
{
	fa[u]=Fa;
	int k=0;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==Fa)
			continue;
		sumc[u]+=c[v];
		dfs(v,u);
		++k;
	}
	solve(u,0,k);
	solve(u,1,k);
}
int solve_greedy()
{
	int greedy_ans=0;
	for(int u=1;u<=n;++u)
		if(c[u])
		{
			greedy_ans+=max(d[u],0);
			for(int i=head[u];i;i=nx[i])
			{
				int v=to[i];
				d[v]-=c[u];
			}
		}
	for(int u=1;u<=n;++u)
		if(!c[u])
			greedy_ans+=max(d[u],0);
	cout<<greedy_ans<<endl;
	return 0;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		d[i]=read();
	for(int i=1;i<=n;++i)
		c[i]=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	if(n>2000)
		return solve_greedy();
	for(int i=0;i<=n;++i)
		for(int j=0;j<=10000;++j)
			g[i][j]=inf;
	g[0][0]=0;
	dfs(1,0);
	cout<<f[1][0]<<endl;
	return 0;
}