设计族谱树数据结构
Overview
This question evaluates a candidate's ability to design and implement complex graph-based data structures and algorithms, including representation of a family DAG with constraints, cycle detection, ancestor/descendant queries, DAG-based closest-common-ancestor computation, dynamic parent/child linking and unlinking, indexing for fast queries, and serialization while considering performance targets for N ≤ 1e5 and Q ≤ 1e5. It is commonly asked in the Coding & Algorithms domain to assess proficiency in graph theory, algorithmic complexity and trade-offs, incremental update and cycle-detection strategies, and both conceptual understanding of DAG semantics and practical application of scalable, online data-structure design.
设计一个族谱树（家谱）数据结构来表示血缘关系：每个 Person 节点具有唯一 id、姓名、可选出生/死亡年份与性别；每个节点至多关联两位父母，允许多个子女；整体应为有向无环图（父母→子女），禁止形成环。需要支持以下操作并给出关键函数的伪代码、时间/空间复杂度分析与单元测试样例：
- add_person(id, attrs)：新增人物。
- link_parent_child(parent_id, child_id)：建立父母-子女关系，需校验年龄合理性与不成环；支持未知父母占位与随后补充；支持收养导致的多父母但仍限制为最多两位。
- ancestors(id, k)：返回指定人物向上追溯至多 k 代的祖先（按代数分层并可选按出生年份排序）。
- descendants(id, k)：返回向下至多 k 代的后代。
- is_ancestor(a, b)：判断 a 是否为 b 的祖先。
- closest_common_ancestor(a, b)：在允许双亲的 DAG 上，定义两者到共同祖先的代数和最小者为“最近共同祖先”，返回所有距离最短的共同祖先及各自距离。
- siblings(id)：返回同父或同母（或双亲相同）的兄弟姐妹。
- degree_of_kinship(a, b)：以边为代价，计算最短亲缘路径长度及路径（允许经由祖先或后代）。
- unlink_parent_child(parent_id, child_id) 与 remove_person(id)：支持删除关系与人物（需描述如何保持结构一致与索引更新）。 1
- serialize()/deserialize()：将家谱持久化与恢复。 请说明：
- 底层数据结构选择（邻接表、反向边、索引），以及在 N≤1e5、Q≤1e5 的在线更新场景下的复杂度目标；
- 环检测策略（增量式 DFS/并查集带时间戳/拓扑序维护等）；
- 最近共同祖先在 DAG 上的求解思路（如由两节点同时向上 BFS/双向搜索/预处理祖先层级位图或稀疏索引的权衡）；
- 不完整信息（未知父母）、收养/继亲、多胎出生的表示与查询一致性；
- 示例输入输出：给出 5–10 条人物与关系，演示上述每个操作的结果。