#19251. 细胞的谱系树
细胞的谱系树
你好,我是阿西莫夫。
在生物学中,最完美的二叉树结构莫过于 细胞分裂(Cell Division)。
从一个受精卵(Zygote)开始,进行有丝分裂,一分为二,二分为四……每一次分裂,都像是计算机科学中二叉树的一次“生长”。在发育生物学中,科学家们会绘制 “细胞谱系树(Cell Lineage Tree)”,用来追踪每一个细胞的祖先和后代。
为了考察二叉树(Binary Tree)的存储、深度优先搜索(DFS)以及树高/子树大小的计算,我为你构思了这道题目。
[OI 题库] 细胞分化的“谱系树” (The Cell Lineage Tree)
题目背景
“生命始于一,演化为万物。”
在发育生物学的实验室里,你正在通过显微镜观察一种秀丽隐杆线虫(C. elegans)的胚胎发育过程。 这种生物的发育过程非常精确,每一个细胞的分裂命运都是注定的。
我们将受精卵标记为 1号细胞。 它会分裂成两个子细胞(左子细胞和右子细胞)。这两个子细胞可能会继续分裂,也可能停止分裂(进入期分化为特定组织)。
记录员已经整理出了 个细胞的分裂关系表。请你通过编程,分析这棵“细胞谱系树”的两个关键指标:
- 繁衍规模:最终一共有多少个细胞(即树的节点总数)?
- 分化代数:从受精卵开始,最长的一条分裂链经历了多少轮分裂(即树的最大深度)?
题目描述
给定一个包含 个节点的二叉树结构。节点编号从 到 。 1号节点 是根节点(受精卵)。
输入将给出每个节点的左孩子和右孩子编号。
- 如果一个节点的子节点编号为
0,表示该位置没有分裂(为空)。
请计算并输出:
- 以 1 号节点为根的子树大小(节点总数)。
- 这棵树的深度(根节点深度为 1)。
输入格式
第一行一个整数 ,表示记录在案的细胞数量。 接下来 行,第 行包含两个整数 ,分别表示 号细胞 的左子细胞和右子细胞的编号。 (若为 0,则表示无对应子细胞)。
输出格式
一行,包含两个整数,中间用空格分隔。 分别表示节点总数和最大深度。
样例数据
样例 1
5
2 3
4 5
0 0
0 0
0 0
5 3
解析:
- 1 分裂出 2, 3
- 2 分裂出 4, 5
- 3, 4, 5 不再分裂
- 结构:
1
/
2 3 /
4 5 - 总数:5 个。
- 深度:1 -> 2 -> 4 (共 3 层)。
样例 2 (单链结构)
4
2 0
0 3
4 0
0 0
4 4
解析:
- 1 -> 2 -> 3 -> 4
- 这是一条像链表一样的树。
- 深度为 4。
数据范围
- 数据保证能构成一棵合法的以 1 为根的树,无环。