$O(n^2)$ 树形背包 @ Wings            分类 ACM
发布于 星期六, 九月 4 日, 2021 年
更新于 星期四, 十一月 25 日, 2021 年

(zzs讲课没听, vp遭殃)

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

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

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

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背包滚动数组转移方式, 写成代码长这样:

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--)	// 由于 u 可以不选, 所以 k 需要枚举到 0
			for (int x = 0; x <= sz[v]; x++) {
				// 因为 dp(u, 0, 1) = inf, 所以转移过来一定是 inf, 合在一起写没问题
				// 如果是取 max, dp(u, 0, 1) 就会出问题, 可以第三维分开枚举转移
				// 当然也可以认为 dp(u, 0, 1) 不存在, 设为 -inf, 然后合在一起写
				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];
	}
}

UPD: 上面的部分是错的.

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 数组, 由当前行转移, 做完以后给他复制回去就行.

下面是正确的板子:

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];
	}
}

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星
  21. [2021 ICPC 沈阳 105名 真银尾]
  22. [2021 CCPC 哈尔滨 银牌]
  23. [2021 ICPC 南京 铜牌]

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch