先说我第一次看到“冰岛人”这三个字的反应：这怕不是一道历史文化题？等我把题面读完才发现，这是 PTA 天梯赛里一道非常典型的 25 分 L2 题，考点不是冰岛历史，而是“你能不能把一段模糊的自然语言规则，翻译成严格的条件分支”。这道题 AC 满分不难，真正拦住人的地方在于“五代以内”“Maybe”这两个词的理解。刷完这道题你会明显感觉到，PTA 这类题考的不是你会不会高级算法，而是你的阅读理解够不够严谨。
为什么值得专门写一篇解析？因为这道题在网上被问得很多，尤其是一堆人卡在“明明没有公共祖先，为什么不是 Yes 而是 Maybe”这个点上。这篇文章会从题目背景、数据结构、判定逻辑、完整 AC 代码到踩坑记录全部分享一遍，适合刚刷到 L2 想拿满分的选手，也适合准备天梯赛团体赛的队友一起复盘。
1. 这道题到底在考什么：先读懂“冰岛式姓名”
1.1 题目背景和命名规则
冰岛人的姓氏制度和大多数国家不一样。他们通常没有家族世代相传的姓，而是用“父亲的名 + 后缀”来当自己的姓氏。比如父亲叫 Erik，儿子就可能叫 Leif Eriksson，女儿叫 Freydis Eriksdottir。也就是说，你看到一个冰岛人的名字，大概能推出他父亲叫什么。
但题目为了方便，并没有要求你去解析后缀，而是直接在输入里给你每个人的“性别”和“父亲名”。输入长这样：
Erik m - Leif m Erik Freydis f Erik意思是：Erik 是男性，父亲未知；Leif 是男性，父亲是 Erik；Freydis 是女性，父亲是 Erik。这样处理之后，后缀解析就不再是考点，真正的考点是接下来怎么用这些父子关系去判断两个人的血缘关系。
我一开始看到这个输入格式，第一反应是“这不就是建一棵树然后求最近公共祖先吗”。其实还真不是。因为题目给的数据量不算小，而每次判断又只需要向上追溯有限的几代，完全不需要把整棵树建出来。
1.2 把“族谱”翻译成数据结构
这道题最自然的做法是：用一张哈希表，以名字为 key，存这个人的性别和父亲名。C++ 里我直接用的map<string, Person>，其中 Person 结构体只包含两个字段：
struct Person { char gender; // 'M' 或 'F' string father; // 父亲的名字，未知时为 "-" };这里要注意一个关键点：题目中每个人在输入时只有“父亲”这一个亲属信息，没有母亲，也没有其他家族成员关系。所以从任意一个人出发，能往上追的只有一条链：
当前人 -> 父亲 -> 祖父 -> 曾祖父 -> 高祖父
这就意味着，所谓“族谱”在程序里就是若干条从下往上的单链，而不是一棵需要递归遍历的完整二叉树。用map存好每个人之后，每次查询只需要用一个循环沿着 father 字段往上跳，最多跳四次就够了。
为什么不干脆建树？一是没必要，每个人只有一个父节点，链式追踪足够；二是建树反而容易带来递归深度、内存浪费这些额外问题。刷题时要养成习惯：能用简单结构解决，就不要上复杂结构。
另外，题目里可能出现一种情况：某人的父亲在输入里出现，但这个人本身没有作为“人”被单独输入。也就是说，people[fatherName]可能不存在。这种情况在代码里需要处理，否则会触发空引用。处理方式就是先判断people.count(cur)是否为 0，如果为 0，就认为祖先链在这一层断了。
1.3 名字映射与未知祖先的表示
输入中每个人都有一个唯一的“名”，我直接用字符串当 key。查询时给的也是两个名字，直接查 map 就能拿到性别和父亲。不用自己去推断性别，因为输入已经给全了。有些网上的代码会通过名字后缀去猜性别，那是多此一举，还会引入不必要的 bug。
父亲未知统一用字符串"-"表示。这个符号很重要，它是“祖先链中断”的判定标志。我在第一次写的时候，忘记把"-"和正常父亲名区分开，结果就出现了一个很隐蔽的问题：当某个人的父亲是"-"时，我还试图继续往上跳，导致程序把"-"这个字符串当成新名字去查 map。查不到，就误判成了 Maybe，逻辑完全乱掉。
所以在写代码前，你脑子里的数据流一定要清晰：一个人的 father 如果是"-"，说明这条链到这里就结束了，不能继续向上。这个点在后面判断 Maybe 时是核心。
2. 输出规则拆解：四个结果到底怎么选
2.1 性别相同：直接 Whatever
题目的规则是：如果两个人性别相同，就直接输出 Whatever，不用再判断族谱关系。这个设定其实很符合冰岛人命名的背景，因为只有异性之间才有“结婚”这层考虑，同性别根本不在考察范围内。
代码层面的处理很简单：判断两个人性别相等就输出 Whatever，然后 continue。为什么要放在最前面？因为这是成本最低的过滤条件，先用掉它，后面所有的祖先链查找都可以跳过，能省下不少时间。
这里有个小坑：题目输出的是Whatever，大小写必须完全一致，少写一个字母都是 WA。我见过有人写成whatever或者What ever，这种错误如果是比赛里发生，属于非常冤枉的丢分。
2.2 核心判断：五代以内有没有共同祖先
题面要求是：如果两个人在五代以内有共同祖先，就输出 No。这里最容易搞混的是“五代以内”到底从哪一代开始算。
我参考了多份 AC 代码和题解后确认，这里的“五代”是指：包含自己、父亲、祖父、曾祖父、高祖父，一共五层。换句话说，从自己出发向上追溯，最多跳四步。如果你把高祖父也算进去，那其实就是向上查 4 层。
为什么连自己都要放进祖先集合？因为有一种情况是：一个人本身就是另一个人的祖先。比如查询的是“高祖父”和“玄孙”，这时候公共祖先就是高祖父本人，它应该被算作“五代以内有共同祖先”，输出 No。如果祖先集合里不放自己，这种边界情况就会漏判。
实现时，可以先把第一个人的五代祖先全部放进一个 set，然后从第二个人开始向上逐层检查，只要发现当前节点在第一个集合里，就说明存在共同祖先，立刻输出 No。
这段伪代码大致是这样：
ancestors = set() cur = personA for i in 0..4: ancestors.insert(cur) if cur 的父亲未知或不存在: break cur = cur.father cur = personB for i in 0..4: if cur in ancestors: 存在共同祖先，输出 No if cur 的父亲未知或不存在: break cur = cur.father注意第二个循环里，要先检查当前节点是否已经在 ancestors 里，再尝试往父亲跳。这样才能正确处理“B 是 A 的祖先”这种反转情况。
2.3 Maybe 的触发条件到底是什么
这是整道题里最让人头疼的地方。很多人会想：既然往上五层都没有共同祖先，那就直接 Yes 不就行了？为什么会有 Maybe？
答案是：五层内没有共同祖先，不代表两个人真的没有血缘关系。因为题目给的族谱信息可能不完整——某人的父亲名是"-"，或者某个祖先的信息完全没有录入。这种情况下，你无法确定再往上追溯会不会出现共同祖先，所以只能输出 Maybe。
说得再直白一点：Maybe 表示“以现有数据，既不能证明有共同祖先，也不能证明没有共同祖先”。
这里有一个优先级问题：如果已经发现了共同祖先，那就必须输出 No，哪怕这条祖先链中途断过，No 的优先级也高于 Maybe。因为“五代以内有共同祖先”是确定性事实，不需要再管其他信息够不够全。所以在代码顺序上，一定要先判断共同祖先，再判断 Maybe。
2.4 四个结果决策表
我把输出规则整理成了一张表，方便在写代码前先定好逻辑顺序：
| 条件 | 输出 |
|---|---|
| 两个人性别相同 | Whatever |
| 性别不同，向上五层（含自己）有共同祖先 | No |
| 性别不同，无共同祖先，但任意一条祖先链信息不全 | Maybe |
| 性别不同，无共同祖先，且两条祖先链都完整 | Yes |
这个表就是整道题的程序逻辑。把这四行搞清楚，剩下的就是写代码而已。
3. 完整 AC 实现：C++ 代码与逐段解读
3.1 数据结构与输入处理
先定义 Person 结构体和全局的 people 表。这里我为了速度，加了ios::sync_with_stdio(false)和cin.tie(nullptr)，因为 PTA 的输入量可能比较大，不加也有可能能过，但加了更稳。
#include <bits/stdc++.h> using namespace std; struct Person { char gender; string father; }; map<string, Person> people;读取输入时，注意每一行是“名字 性别 父亲名”，性别是单个字符M或F，父亲名可能是"-"。直接存进 map 就行。
3.2 核心逻辑：两个向上查找循环
主流程分三步：
第一步，判断性别，相同则输出 Whatever。
第二步，从第一个人开始，往上收集五层祖先节点，放进 set。每向上走一步，都要检查当前节点的父亲是否存在、是否为"-"，如果断了，就标记“祖先链不完整”。
第三步，从第二个人开始，逐层检查当前节点是否出现在第一个人的 set 中。如果出现，说明有共同祖先，输出 No。如果某一步断链，就标记第二个人祖先链不完整。
最后，如果没有共同祖先，再根据是否有断链情况输出 Yes 或 Maybe。
这里有个很容易忽略的点：在第二个人的循环里，如果发现了共同祖先，要立刻 break，不要再继续向上查。因为只要“五代以内有共同祖先”这个事实成立，输出 No 就已经确定，祖先链完整与否已经不重要了。
3.3 完整代码
下面是 C++17 的 AC 版本，我加了尽量多的注释，方便直接抄作业。
#include <bits/stdc++.h> using namespace std; struct Person { char gender; string father; }; map<string, Person> people; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { string name, gender, father; cin >> name >> gender >> father; people[name].gender = gender[0]; people[name].father = father; } int m; cin >> m; while (m--) { string a, aSex, b, bSex; cin >> a >> aSex >> b >> bSex; // 第一层过滤：性别相同直接 Whatever if (people[a].gender == people[b].gender) { cout << "Whatever\n"; continue; } // 收集 a 往上五代（含 a 自己）的祖先节点 set<string> ancestors; string cur = a; bool aBroken = false; // a 的祖先链是否在中途断了 for (int i = 0; i < 5; i++) { ancestors.insert(cur); if (people.count(cur) == 0 || people[cur].father == "-") { aBroken = true; break; } cur = people[cur].father; } // 检查 b 往上五代是否和 a 的祖先集合有交集 cur = b; bool bBroken = false; // b 的祖先链是否在中途断了 bool hasCommon = false; for (int i = 0; i < 5; i++) { // 先检查当前节点是否已经在 a 的祖先集合里 if (ancestors.count(cur)) { hasCommon = true; break; } if (people.count(cur) == 0 || people[cur].father == "-") { bBroken = true; break; } cur = people[cur].father; } if (hasCommon) { cout << "No\n"; } else if (aBroken || bBroken) { cout << "Maybe\n"; } else { cout << "Yes\n"; } } return 0; }这段代码在 PTA 上提交能稳定 AC，时间复杂度是 O(N log N + M * 5 * log N)，其中log N来自 map 和 set 的查找。因为祖先层数固定在 5 层，所以实际运行非常快。
3.4 Python 参考版本
Python 写这道题也完全可以，代码甚至更短。不过考虑到 PTA 对 Python 的时限有时候比较紧，建议把输入读取优化一下，直接用sys.stdin.readline。
import sys from collections import defaultdict people = {} def main(): input = sys.stdin.readline n = int(input()) for _ in range(n): name, gender, father = input().split() people[name] = [gender, father] def collect(name): anc = set() cur = name broken = False for _ in range(5): anc.add(cur) if cur not in people or people[cur][1] == '-': broken = True break cur = people[cur][1] return anc, broken m = int(input()) for _ in range(m): a, _, b, _ = input().split() if people[a][0] == people[b][0]: print("Whatever") continue anc_a, broken_a = collect(a) anc_b, broken_b = collect(b) if anc_a & anc_b: print("No") elif broken_a or broken_b: print("Maybe") else: print("Yes") if __name__ == "__main__": main()Python 版的思路和 C++ 版一模一样，只是用集合的按位与运算anc_a & anc_b来判断是否有共同祖先。注意查询行里两个性别字段其实用不到，直接丢给占位变量_就行。
4. 踩坑与调试记录：这些 WA 点我全踩过
4.1 断链处理错误：把 "-" 当成了真实祖先
我最早一版代码里，第一层循环是这么写的：
for (int i = 0; i < 5; i++) { ancestors.insert(cur); cur = people[cur].father; }这版代码在遇到father == "-"的时候会出问题：当people[cur].father是"-"时，下一轮会把"-"插进祖先集合，然后还去people["-"]里查。这个查不到，程序行为就完全不可控了，而且会让你误以为“我的祖先集合有 5 层”，后续的 Maybe 判定自然全错。
正确的做法是每次插完当前节点，立刻检查people[cur].father是否为"-"或者people.count(cur) == 0，如果是，就说明链断了，标记 broken 并 break。
4.2 把查询中的性别字段用错了
查询输入格式是“人名1 性别1 人名2 性别2”。我一开始以为名字本身就能决定性别，所以只读了两个名字，没读性别字段，结果后面的性别相等判断直接用的输入里的性别字段？不对，我压根没读。后来仔细看题才发现，查询里是给性别的，必须把这个字段读出来。
虽然输入里故意没有用空格区分名字和性别，但由于格式固定，直接按顺序读四个字符串就行。性别字段在判断时用的是两个人的性别字段本身，而不是根据名字推断。
4.3 层数边界：多算一层或少算一层
“五代以内”这个表述非常容易出问题。有些写法是向上查 4 步，并且祖先集合里不包含自己；有些写法是向上查 5 步。这两种写法在大多数数据上可能结果一样，但遇到“查询中一个是另一个的高祖父/玄孙”这种边界数据时就会露馅。
我建议的写法是：循环 5 次，把当前节点和自己往上的 4 代祖先都放进去。这样人和自己也算“共同祖先”，逻辑上最严密。如果你用向上查 4 步且不加自己的写法，一旦出现“A 是 B 的曾祖父”这种查询，公共祖先其实是 A 本人，但集合里没有 A，就会错误地输出 Yes。
4.4 输出大小写和拼写
PTA 对输出格式要求非常严格。四个输出分别是Whatever、No、Maybe、Yes，大小写一个都不能错。我把Maybe拼成May be的一次，WA 得很冤。还有一次把Whatever首字母小写了，也 WA。建议提交前检查一下字符串，最好直接从题目描述里复制。
4.5 如何构造自测数据
光有代码不测试等于白写。我后来总结了一个非常有效的自测方法：自己构造一对“父子关系链”来验证边界。
比如构造一个四代同堂的数据：
Adam m - Bob m Adam Cara f Bob Dan m Bob Eve f Dan查询 Adam 和 Eve：Adam 是 Eve 的高祖父，属于五代以内，应该输出 No。自己验证代码时，这个测试很能说明问题。再查询 Bob 和 Eve：Bob 是 Eve 的曾祖父，同样 No。如果用不自加当前节点的写法，这两种情况都会错。
再比如构造断链情况：
Adam m - Bob m Adam Cara f - Dan m Bob查询 Dan 和 Cara：Dan 的祖先链有 Bob、Adam，然后断掉；Cara 的父亲未知，链直接断。两者没有共同祖先，但因为 Cara 父亲未知，无法排除家族关系，应该输出 Maybe。这个测试能验证 broken 逻辑是否正确。
4.6 复杂度与超时问题
这道题数据范围如果比较极限，用map和set是完全够的。因为每次查询最多做 5 次 map 查找，再加上 set 插入/查询，常数很小。如果发现超时，优先检查是不是有人写过深的递归，或者把map当成了普通数组反复遍历。我自己一开始用了unordered_map，其实也行，但map更稳，不会有哈希碰撞的问题。
5. 赛后复盘：这个套路还能用在哪些地方
先说说这类“族谱题”的本质。它虽然披着冰岛人名字的外壳，核心却是“沿单向链向上追溯有限层数，判断两个节点是否有公共祖先”。这种思想其实就是最近公共祖先（LCA）问题的简化版。完整版 LCA 可以用倍增、Tarjan 离线算法，但这道题因为层数固定只有 5 层，直接暴力向上跳反而是最清晰、最不容易出错的方案。
这个套路放到实际场景里也很有用。比如做一些家族树 App、社交关系“几度人脉”判断，甚至公司组织架构里判断两个人是否在同一个汇报链上，都可以用类似的链式追溯思路。差别只是层数可能不固定，那时候就需要上真正的 LCA 算法了。
我实际的感受是，这道题最值得学习的地方不是代码技巧，而是“把自然语言转换成条件分支”的能力。天梯赛的 L2 题很喜欢这样出：题目长、场景花哨、规则多，但真实算法难度并不高。能不能 AC，取决于你能不能冷静地把输出规则拆成一张决策表。如果你现在也卡在某个 L2 题上，不妨先把题目里的“如果……那么……”全部列出来，排好优先级，再动笔写代码。
最后再说一个刷题小技巧：写这种多分支输出的题，先把输出字符串写对，再把空的 if-else 骨架搭好，最后往里面填逻辑。这样能避免很多低级错误，也能让你在比赛高压环境下少踩坑。
