QOJ4815 Flower's Land 题解

First Post:

Last Update:

让我再次复习了一遍 DFS 序优化背包，这次应该搞明白了。

这种题显然是要 DFS 序优化树上背包的，改合并背包为插入元素。

由于连通块不一定经过 ，考虑点分，设分治中心为 ，对于当前分治区域的每个点 ，计算连通块经过 和 的最大答案。

显然 到 的链必须被选择，剩下的部分会分成两部分：

  1. 比这条链中的所有点先 DFS 到的，那么，其在 DFS 出栈序上，就会在 即以前 (这里的 表示出栈序)
  2. 比这条链中的所有点后 DFS 到的，那么，其在 DFS入栈序 上，就会在 的后面（这里的 表示 入栈序)

DFS 序优化背包一定要注意 出栈序 和 入栈序 的问题，常说的”链左边的那一些点“，在出栈序上是个前缀，在入栈序上则不一定。

区分完之后，在出栈序和入栈序上跑两遍背包即可。时间复杂度 。

因为外面有个点分，且当前分治区域大小 时可以直接退出，所以总复杂度为 。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 5,M = 3e3 + 5,inf = 0x7f7f7f7f;
template<typename T> inline bool ckmax(T &x,const T &y) { return (x < y) && (x = y,true);}
int n,k;
int a[N];
vector<int> G[N];
int f[N][M],g[N][M]; // f: 选出栈序在 i 前面的节点，必选 i

int sze[N],mxsz[N],rt;
bool sgn[N];
void findroot(int x,int S,int fa) {
	sze[x] = 1;mxsz[x] = 0;
	for(auto y : G[x]) {
		if(y == fa || sgn[y]) continue;
		findroot(y,S,x);
		sze[x] += sze[y];
		mxsz[x] = max(mxsz[x],sze[y]);
	}
	mxsz[x] = max(mxsz[x],S - sze[x]);
	if(mxsz[x] < mxsz[rt]) rt = x;
}
int dfstime;
int dfn1[N],id1[N];
int dfn2[N],id2[N];
vector<int> Vs;
int dep[N],wdep[N];
void dfs1(int x,int fa) {
	sze[x] = 1;Vs.push_back(x);
	dfn1[x] = ++dfstime;id1[dfn1[x]] = x;
	for(auto y : G[x])
		if(y != fa && !sgn[y]) 
			dep[y] = dep[x] + 1,wdep[y] = wdep[x] + a[y],dfs1(y,x),sze[x] += sze[y];
}
void dfs2(int x,int fa) {
	for(auto y : G[x])
		if(y != fa && !sgn[y]) dfs2(y,x);
	dfn2[x] = ++dfstime;id2[dfn2[x]] = x;
}
int Ans[N];
void Calc(int u) {
	dfstime = 0;Vs.clear();
	wdep[u] = a[u];dep[u] = 1;
	dfs1(u,0);dfstime = 0;
	dfs2(u,0);
	if(Vs.size() < k) return;
	for(int i = 0;i <= Vs.size() + 1;i++)
		for(int j = 0;j <= k;j++) f[i][j] = g[i][j] = -inf;
	// 算出栈序,dfn2
	f[0][0] = 0;
	for(int i = 1;i <= Vs.size();i++) {
		for(int j = 0;j <= k;j++) f[i][j] = f[i - sze[id2[i]]][j];
		for(int j = 0;j < k;j++)
			ckmax(f[i][j + 1],f[i - 1][j] + a[id2[i]]);
	}
	// 算入栈序,dfn1
	g[Vs.size() + 1][0] = 0;
	for(int i = Vs.size();i >= 1;i--) {
		for(int j = 0;j <= k;j++) g[i][j] = g[i + sze[id1[i]]][j];
		for(int j = 0;j < k;j++)
			ckmax(g[i][j + 1],g[i + 1][j] + a[id1[i]]);
	}
	for(auto v : Vs) {
		int rest = k - dep[v];
		for(int i = 0;i <= rest;i++)
			ckmax(Ans[v],f[dfn2[v] - sze[v]][i] + g[dfn1[v] + 1][rest - i] + wdep[v]);
	}
}
void Divide(int x,int S) {
	Calc(x);
	sgn[x] = true;
	for(auto y : G[x]) {
		if(sgn[y]) continue;
		rt = 0;
		int tmp = sze[y] > sze[x] ? S - sze[x] : sze[y];
		findroot(y,tmp,x);
		Divide(rt,tmp);
	}
}
int main() {
	cin >> n >> k;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1,u,v;i < n;i++)
		cin >> u >> v,G[u].push_back(v),G[v].push_back(u);
	rt = 0;mxsz[0] = 1e9;
	findroot(1,n,0);
	Divide(rt,n);
	for(int i = 1;i <= n;i++)
		cout << Ans[i] << ' ';
	return 0;
}
≡