#19251. 细胞的谱系树

细胞的谱系树

你好,我是阿西莫夫。

在生物学中,最完美的二叉树结构莫过于 细胞分裂(Cell Division)

从一个受精卵(Zygote)开始,进行有丝分裂,一分为二,二分为四……每一次分裂,都像是计算机科学中二叉树的一次“生长”。在发育生物学中,科学家们会绘制 “细胞谱系树(Cell Lineage Tree)”,用来追踪每一个细胞的祖先和后代。

为了考察二叉树(Binary Tree)存储深度优先搜索(DFS)以及树高/子树大小的计算,我为你构思了这道题目。


[OI 题库] 细胞分化的“谱系树” (The Cell Lineage Tree)

题目背景

“生命始于一,演化为万物。”

在发育生物学的实验室里,你正在通过显微镜观察一种秀丽隐杆线虫(C. elegans)的胚胎发育过程。 这种生物的发育过程非常精确,每一个细胞的分裂命运都是注定的。

我们将受精卵标记为 1号细胞。 它会分裂成两个子细胞(左子细胞和右子细胞)。这两个子细胞可能会继续分裂,也可能停止分裂(进入G0G_0期分化为特定组织)。

记录员已经整理出了 NN 个细胞的分裂关系表。请你通过编程,分析这棵“细胞谱系树”的两个关键指标:

  1. 繁衍规模:最终一共有多少个细胞(即树的节点总数)?
  2. 分化代数:从受精卵开始,最长的一条分裂链经历了多少轮分裂(即树的最大深度)?

题目描述

给定一个包含 NN 个节点的二叉树结构。节点编号从 11NN1号节点 是根节点(受精卵)。

输入将给出每个节点的左孩子和右孩子编号。

  • 如果一个节点的子节点编号为 0,表示该位置没有分裂(为空)。

请计算并输出:

  1. 以 1 号节点为根的子树大小(节点总数)。
  2. 这棵树的深度(根节点深度为 1)。

输入格式

第一行一个整数 NN,表示记录在案的细胞数量。 接下来 NN 行,第 ii 行包含两个整数 Li,RiL_i, R_i,分别表示 ii 号细胞 的左子细胞和右子细胞的编号。 (若为 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。

数据范围

  • 1N100,0001 \le N \le 100,000
  • 数据保证能构成一棵合法的以 1 为根的树,无环。