2020 CCPC 秦皇岛 K.Kingdoms Power @ Wings            分类 ACM
发布于 星期五, 十二月 11 日, 2020 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

$T$组测试. $n$个点的有根树, 根为$1$, 初始根被占领, 且可以无限从根派兵去占领其他节点, 兵可以沿着边走(无向边, 可以返回来走), 每走一次花费为$1$. 问占领所有点最少需要多少花费.

$1 \le T \le 10^5, 1 \le n \le 10^6)$

题解

设$dp_1(u)$为 点$u$有一个并, 只用这一个兵走完以$u$为根的子树, 并且回到$u$需要的步数; $dp_2(u)$为 从根节点$(1)$出若干个兵, 走完$u$这棵子树, 并且兵停在某些叶子需要的最小步数.

答案很显然是$dp_2(1)$

下面想转移:

很容易转移$dp_1(u)$,

$$dp_1(u) = \sum_{v \in SON_u} (dp_1(v) + 2)$$

很显然, 这个兵往下走需要一次, 走完后回来需要一次, 所以一条边加两次.

如何转移$dp_2$呢??

首先有一个树形$dp$的常用性质:

如果对一个节点$u$, 当前已经考虑完了若干个儿子, 并且完成了儿子到$u$的转移, 即得到了"部分"的$dp(u)$. 这时的$dp(u)$是有意义的, 即"$u$和已经做完的儿子构成的子树(为方便, 称它为’当前子树')的$dp$值", 如图:

u的某个当前子树

这样就可以合理利用"已经做完的所有儿子", 而不是枚举做完的儿子. 当然前提是状态要定义得好.

回到本题, 考虑当前儿子$v$, 可能有三种情况:

  1. 做完的儿子中的某一个兵回到$u$, 它再走$v$. 注意这样的话可以用他来"替换"一个$dp_2(x) \mid x \in Tree_v$的花费(停在$Tree_v$的其他兵的花费是直接算的$dp_2$, 从根下来的, 不与当前做法冲突)

  2. $v$做完后, 一个兵回到$u$, 去走"做完"的儿子(利用"当前子树", 即可考虑所有"做完"的儿子[为什么打引号呢? 因为这一步改变了"当前子树"的策略, 也就是说, 当前子树的当前策略并不是最终策略])

  3. 直接从根新派若干个兵走完$v$

对应的三个花费分别是:

$$ \begin{aligned} & dp_1(u) + dp_2(v) \newline & dp_2(u) + dp_1(v) + 2 \newline & dp_2(u) + dp_2(v) \end{aligned} $$

前两个看着很迷?

解读一下, 以第一个决策的花费为例:

$dp_2(v)$被分为了两个部分, $1 — u — Tree_v$; 而$dp_1(u)$只是$CurrentTree_u — back\ to\ u$一个部分, 重新组合一下, 变成$1 — CurrentTree_u — back\ to\ u — Tree_v$, 这样就是实际上的路线了

第二个也是同理拆分重组

结合上述分析和方程, 再理解一下决策…

可以发现, 决策1和2恰好是"对称"的, 考虑了全部的"兵回到$u$再走其他儿子"的情况; 同时有第三个决策, 考虑了从根下来的情况, 弥补了前两个方程"只是一个兵在走"的不足. 所以, 这种转移考虑到了所有的情况, 是合理且巧妙的.

那么新的当前子树$dp_2$的值就对上述三种决策的花费最小即可.

最后确定边界条件. 树形dp的边界是叶子, 但是这里有一个不是常规的树形dp定义法, $dp_2$居然和根扯上了关系. 可以理解为, 结点本身就有一个花费(从根走到该节点的步数, 即深度), 把他加在$dp_2$上即可. $dp_1$的初始值为$0$.

独立思考我绝对想不到这样的做法, 太妙了, 下次补"为什么这么想"吧, 咕咕咕

复杂度$O(n)$

代码
const int maxn = 1e6+10;

int t, n, ans, dp1[maxn], dp2[maxn];
vector<int> son[maxn];

void dfs(int u, int d) {
	dp1[u] = 0;
	dp2[u] = d;
	for (auto v : son[u]) {
		dfs(v, d + 1);
		dp2[u] = min(min(dp1[u] + dp2[v], dp2[u] + dp1[v] + 2), dp2[u] + dp2[v]);
		dp1[u] += dp1[v] + 2;
	}
}

int main() {
	scanf("%d", &t);
	for (int kase = 1; kase <= t; kase++) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			son[i].clear();
		for (int i = 2; i <= n; i++) {
			int f;
			scanf("%d", &f);
			son[f].pb(i);
		}
		dfs(1, 0);
		printf("Case #%d: %d\n", kase, dp2[1]);
	}
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

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 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

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

运动

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

音乐

  • 吉他
  • 词曲
  • 流行

玩具

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

追星

  • VAE
  • Benedict Cumberbatch