O(n^2) 树形背包

Wings 收录于类别 ACM

2021-09-04 2022-02-06 约 1274 字预计阅读 3 分钟次阅读条评论

(zzs讲课没听, vp遭殃)

树形背包首先压了一维, 这个要注意.

设 $dp(u, k)$ 为在以 $u$ 为根的子树中选 $k$ 个点, 且一定选 $u$ 这个点, 子树的最大价值.

代码长这样(这个板子不完全正确的):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void dfs(int u) {
	sz[u] = 1;
	dp[u][1] = a[u];
	for (int v : G[u]) {
		dfs(v);
		for (int k = sz[u]; k; k--)
			for (int x = 1; x <= sz[v]; x++)
				dp[u][x+k] = max(dp[u][x+k], dp[u][k] + dp[v][x]);
		sz[u] += sz[v];
	}
}

注意过程中没有用到非法状态 $dp(u, 0)$.

注意代码中对 $dp(u, m)$ 的第二维并没有全部枚举, 而是枚举考虑过的子树总大小. 所以, 枚举 $k$ 的上限是前 $i$ 个子树的总大小加 $1$ (点 $u$), 然后再枚举当前子树 $v$ 选的个数 $x$, 枚举量为子树大小.

这样复杂度是 $O(n^2)$ 的.

证明:

两个循环, 都是子树大小的枚举量. 可以把两个树看成两个子树中的两个点. 所以总共枚举的点对个数就是总枚举量. 然后一个点对仅会在 lca 处枚举到. 而点对的 lca 唯一, 所以每个点对仅被枚举一次, 故复杂度就是总点对个数, 即 $O(n^2)$

南京那题:

树, 每个点有一个怪, 一个怪有血量 $hp_i$, 开局你可以不用花费代价选择 $m$ 个怪直接消灭掉, 然后需要按从父亲到儿子的顺序消灭其他怪物, 代价为

$$hp_u + \sum_{v \text{上有怪物}} hp_v$$

可以这么考虑, $dp(u, k, 0/1)$ 为以 $u$ 为根的子树, 选了 $k$ 个, 其中 $u$ 是不是活着的, 活着必选, 死了就等于预先把它干掉了.

初始条件 $dp(u, 0, 0) = 0$ (先干掉), $dp(u, 1, 1) = hp(u)$ (活着, 选且必选这个点), 其他为无穷.

转移:

$$dp(u, k, 0) \leftarrow dp(v, k, 0)$$ $$dp(u, k, 0) \leftarrow dp(v, k, 1)$$

上面两个是 $u$ 先被干掉了, 所以不需要多余的代价, 直接儿子转移.

$$dp(u, k, 1) \leftarrow dp(v, k, 0)$$

上面这个是 $u$ 活着, 儿子 $v$ 被干掉了, 不需要多余代价.

$$dp(u, k, 1) \leftarrow dp(v, k, 1) + hp(v)$$

上面这个是 $u, v$ 都活着, 需要多余的代价是 $hp(v)$.

注意01背包滚动数组转移方式, 写成代码长这样:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void dfs(int u, int f) {
	sz[u] = 1;
	dp[u][1] = a[u], dp[u][0] = 0;	// 初值
	for (int v : G[u]) if (v != f){
		dfs(v, u);
		for (int i = 0; i <= sz[u] + sz[v]; i++) tmp[i] = 0;
		for (int i = sz[u]; i >= 0; i--)    // 是否必选一个决定枚举到1还是0
			for (int j = 0; j <= sz[v]; j++)// 同上
				tmp[i+j] = max(tmp[i+j] dp[u][i] + dp[v][j]);
		sz[u] += sz[v];		// 合并
		for (int i = 0; i <= sz[u]; i++) dp[u][i] = tmp[i];
	}
}

注意, 不要写成这样:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void dfs(int u) {
	sz[u] = 1;
	dp[u][1][1] = hp[u];
	dp[u][0][0] = 0;
	for (int v : G[u]) {
		dfs(v);
		for (int k = sz[u]; ~k; k--)
			for (int x = 0; x <= sz[v]; x++) {
				dp[u][k+x][1] = min(dp[u][k+x][1], dp[u][k][1] + min(dp[v][x][1] + hp[v], dp[v][x][0]));
				dp[u][k+x][0] = min(dp[u][k+x][0], dp[u][k][0] + min(dp[v][x][1], dp[v][x][0]));
			}
		sz[u] += sz[v];
	}
}

看这句转移:

1

	dp[u][x+k] = max(dp[u][x+k], dp[u][k] + dp[v][x]);

这个东西乍一看好像没啥问题, 但是, 如果 x 或者 k 可以取0, 那么就会有 “自己转移自己” 的情况. 这显然是不合理的. 然而, 树形背包每一个点, 都是一个单独的 01 背包. 这个方程是拿滚动数组滚掉了一维. “这个点从上一层的这个点转移过来” 才是合法并且必要的转移. 举个例子, 假如 $x = k = 0$, 那么有 $dp(u, 0) \leftarrow dp(u, 0) + dp(v, 0)$. 这个方程实际上是, $dp(u, i, 0) \leftarrow dp(u, i-1, 0) + dp(v, s, 0)$, ($s$ 为 $v$ 的儿子个数).

所以, 我们只要想那种不完全滚掉的背包一样, 保留两行, 就可以正确转移了. 由于树形 dp 不好保留上一行, 可以新开一个 tmp 数组, 由当前行转移, 做完以后给他复制回去就行.

下面是正确的板子:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void dfs(int u, int f) {
	sz[u] = 1;
	dp[u][1] = a[u], dp[u][0] = 0;	// 初值
	for (int v : G[u]) if (v != f){
		dfs(v, u);
		for (int i = 0; i <= sz[u] + sz[v]; i++) tmp[i] = 0;
		for (int i = sz[u]; i >= 0; i--)    // 是否必选一个决定枚举到1还是0
			for (int j = 0; j <= sz[v]; j++)// 同上
				tmp[i+j] = max(tmp[i+j] dp[u][i] + dp[v][j]);
		sz[u] += sz[v];		// 合并
		for (int i = 0; i <= sz[u]; i++) dp[u][i] = tmp[i];
	}
}