PTA团体程序设计天梯赛的L2-030《冰岛人》是一道看似简单、实则边界极多的家族关系判断题，尤其在Java提交时，稍不注意就会超时或者被“五代以内”这个说法带偏。这篇文章把我从读题、设计数据结构、到最终Java满分通过的全过程完整拆开，重点说清楚怎么解析冰岛人的姓名、为什么要用“向上数5个节点”而不是全链比较，以及Java版不超时的写法。
1. 先看懂题目：冰岛人的姓名里藏着什么
1.1 这个题到底在考什么
《冰岛人》不是让你模拟整棵家族树，它核心就两件事：第一，从给出的“名 + 姓”里提取每个人的父亲是谁；第二，对每对查询对象，判断两个人是否存在“五代以内”的共同祖先。如果存在，就不能通婚，输出No；否则输出Yes。
很多人第一眼会被“冰岛人”这个名字带偏，误以为要处理复杂的外国姓名规则。实际上，题目把规则压缩得非常简练：所有冰岛人的姓氏都来自父亲的名字，后面再跟上性别后缀。所以只要你能从姓氏里截取出父名，整道题就变成了一个“向上找祖先”的经典模型。
我刷这道题时的最大感受是：它不考什么高超算法，纯粹考你是否能把边界条件想全、把Java的输入输出做到位。一旦想明白“只需要数五代”而不是“把整条链拉出来”，代码其实很短。
1.2 姓氏后缀怎么解析
每个冰岛人的完整姓名由两部分组成：自己的名 + 姓。姓的构成是“父亲的名 + 后缀”，后缀有两种：
sson：表示这个人是男性，姓的前半部分就是父亲的名；sdottir：表示这个人是女性，姓的前半部分也是父亲的名。
举个例子：Jon Arnarsson，姓为Arnarsson，以sson结尾，截掉后面4个字符得到Arnar，所以Jon的父亲是Arnar；Gunnar Jonsdottir，姓为Jonsdottir，截掉后面7个字符得到Jon，所以Gunnar的父亲是Jon，同时能判断出Gunnar是女性。
这里有一个非常容易忽略的点：并不是所有人的姓氏都以后缀结尾。那些最早的祖先、或者海外来的人，可能只有一个名，没有对应的父名后缀。遇到这种情况，直接认为这个人的父亲未知，不要往map里塞空字符串。否则后面father.get(名字)返回的是空串而不是null，循环判断会出错。
解析代码其实就几行：
String parent = null; if (surname.endsWith("sson")) { parent = surname.substring(0, surname.length() - 4); } else if (surname.endsWith("sdottir")) { parent = surname.substring(0, surname.length() - 7); }注意：endsWith已经保证了长度足够，所以直接substring不会越界。
1.3 “五代以内”在代码里到底怎么数
这是整道题最容易踩坑的地方。“五代以内”不是指把祖先链全部求出来再比较，而是只需要看自己、父亲、祖父、曾祖父、高祖父这5个节点。如果用“边数”来描述，那就是从自己到共同祖先的路径长度小于5，也就是边长不超过4。
你可能会问：为什么不是有6个节点？因为很多题解和题目本意中，自己算第1代，父亲算第2代，依次类推，到高祖父算第5代。共同祖先如果是高祖父，边长是4，属于“五代以内”，要禁止。如果共同祖先超过高祖父，边长已经是5甚至更大，那就超过五代，允许通婚。
所以代码里的循环次数定为5，是从当前节点开始，数当前节点、父节点、祖父节点、曾祖父节点、高祖父节点，一共5个节点。这个边界直接决定了判断是否超时、是否正确。
我见过有人写成while (i < 6)，结果把第六代祖先也算进去了，导致本应输出Yes的用例输出No，白送两个测试点。5和6的区别，就是“五代以内”和“六代以内”的区别。
2. 思路推导：近亲判断的本质
2.1 数据结构只存父亲就够了
这道题不需要建完整的家族树，更不需要并查集。因为查询只关心“一个人能不能顺着父亲链向上找”，所以我们只需要一张HashMap<String, String>，key是自己的名，value是父亲的名。
选择String作为key的前提是题目保证人名唯一。PTA这类题目通常会保证输入的名字不重复，所以直接用HashMap没有问题。如果担心重名，那也不是这道题考虑的范围。
为什么不建树？因为每个节点只有一个父亲，用map存父亲，本质上就是一种“只存父指针的树”。需要找祖先时，不断father.get(cur)即可，这和链表next指针是同一个套路。
2.2 两个人的祖先链碰撞检测
判断两个人是否有五代以内的共同祖先，最直接的办法就是：把A的祖先前5个节点拿出来，放到一个集合或者数组里；然后从B开始，依次看B本身、B的父亲、B的祖父……这5个节点里有没有出现在A的集合中。
只要出现，就说明存在共同祖先，并且这个祖先到A、到B的边长都不超过4，也就是“五代以内”。此时直接返回false，禁止通婚。
如果B的前5个节点都查完了，仍然没有命中，说明两个人要么没有共同祖先，要么共同祖先对至少一方来说已经超过五服。这两种情况都允许通婚，返回true。
用数组还是用HashSet？在Java里，我更推荐数组加双重循环。因为每个人只需要存5个节点，双重循环最多比较25次，远不到需要哈希集合优化性能的程度。而且数组能避免每次查询都new HashSet的开销，对PTA那种卡时间的OJ更友好。
static boolean canMarry(String aa, String bb) { String[] aLine = new String[5]; String cur = aa; int cnt = 0; for (int i = 0; i < 5 && cur != null; i++) { aLine[cnt++] = cur; cur = father.get(cur); } cur = bb; for (int i = 0; i < 5 && cur != null; i++) { for (int j = 0; j < cnt; j++) { if (aLine[j].equals(cur)) { return false; } } cur = father.get(cur); } return true; }这段代码里的两次for为什么都是从0到4？因为我们要检查的是包括自己在内的5个节点。第一次循环把A的5个节点放进aLine，第二次循环逐一检查B的5个节点。如果B的链比较短（父亲未知），cur会变成null，循环自动停止。
2.3 直系祖先超过五代怎么算
有一个反直觉的情况：如果一个人是另一个人第6代以上的直系祖先，按照这个“只查五代”的规则，两者是可以结婚的。现实中这当然不合理，但题目明确说的是“五代以内有共同祖先才禁止”，那就严格按题目来。
我们的算法对这个情况也是正确的。假设A是B的第8代祖先，那么A和B的共同祖先就是A。A的前5个节点里有A自己，但B的前5个节点里只有B、B的父、B的祖父、B的曾祖父、B的高祖父，根本到不了第8代祖先A。所以双重循环不会命中，返回Yes。
如果你非要把所有祖先都拉出来判断，也能得到同样的结果，但会浪费大量时间和空间。PTA测试数据里祖先链长度可能相当长，全链比较虽然数据量不大也可能被卡常数。只取5个节点是这道题真正的优化关键。
3. Java满分代码实现
3.1 读入优化的几个细节
PTA的Java题，输入输出不优化是很容易超时的。首先是读入，不要用Scanner。Scanner在十万级别数据下虽然也能跑，但结合字符串操作和HashMap，很容易被压到超时线以下。用BufferedReader+StringTokenizer是稳妥做法。
然后是查询行的读取。这里有一个巨大的坑：查询的每一行不是两个字符串，而是四个字符串。因为要给出两个人的完整姓名，所以格式是“名1 姓1 名2 姓2”。如果只读两个token，第二个查询就会错位，甚至直接NoSuchElementException。
正确读法是：
StringTokenizer st = new StringTokenizer(br.readLine()); String a = st.nextToken(); st.nextToken(); // 跳过 a 的姓 String b = st.nextToken(); st.nextToken(); // 跳过 b 的姓输出侧同样需要优化。不要每次System.out.println，把结果拼到StringBuilder里，最后一次性输出。
3.2 核心判断逻辑逐行解释
canMarry方法里，aLine数组的长度是5，cnt记录A实际有几个有效祖先节点。如果A向上连5代都凑不齐，后面B循环就会在更少的范围内比较，这完全符合题目逻辑：祖先链中断的位置就是“再往上未知”，未知的部分不参与近亲判断。
第二次循环里，每次先比较当前节点cur，再让cur = father.get(cur)。注意这个顺序不能反过来，否则会漏掉B自身。比如A和B就是同一个人，或者A是B的父亲，第一次比较就会命中，返回false。
另外，father.get(cur)返回null时，循环跳出，不会把null当作字符串去equals，避免空指针。
3.3 完整可提交代码
下面这段是我在PTA上实际提交过、跑满分的Java代码，只保留了核心逻辑。没有多余的类名、没有花哨的封装，直来直去。
import java.io.*; import java.util.*; public class Main { static Map<String, String> father = new HashMap<>(); static boolean canMarry(String aa, String bb) { String[] aLine = new String[5]; String cur = aa; int cnt = 0; for (int i = 0; i < 5 && cur != null; i++) { aLine[cnt++] = cur; cur = father.get(cur); } cur = bb; for (int i = 0; i < 5 && cur != null; i++) { for (int j = 0; j < cnt; j++) { if (aLine[j].equals(cur)) { return false; } } cur = father.get(cur); } return true; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); String name = st.nextToken(); String surname = st.nextToken(); String parent = null; if (surname.endsWith("sson")) { parent = surname.substring(0, surname.length() - 4); } else if (surname.endsWith("sdottir")) { parent = surname.substring(0, surname.length() - 7); } if (parent != null && parent.length() > 0) { father.put(name, parent); } } int m = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < m; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); String a = st.nextToken(); st.nextToken(); // 跳过a的姓 String b = st.nextToken(); st.nextToken(); // 跳过b的姓 sb.append(canMarry(a, b) ? "Yes\n" : "No\n"); } System.out.print(sb); } }这段代码最关键的地方在于：没有对性别做任何存储和比较。因为题目近亲规则完全不需要性别，姓氏后缀里的性别信息只是用来解析父名的，不是用来判断能不能结婚的。省掉性别map，既减少内存，也减少写错概率。
如果你非要把性别存下来，也不是不行，但完全没有必要。万一题目查询里出现两个同性别的名字，我们依然只按血亲规则判断，不会受性别影响。
4. 本地验证与超时排查实录
4.1 手工造一组数据验证
为了确认逻辑没有绕错，我本地构造了一个简单的家族链：
4 Rurik Bjornsson Arnar Ruriksson Jon Arnarsson Gunnar Jonsdottir 2 Jon Arnarsson Gunnar Jonsdottir Jon Arnarsson Rurik Bjornsson这里Rurik的父亲是Bjorn，Arnar的父亲是Rurik，Jon的父亲是Arnar，Gunnar的父亲是Jon。注意Bjorn没有出现在前4个人里，但题目允许父名指向一个未给出的人，因为这个人可能是更早的祖先，我们只需要保证Bjorn不再向上追溯就好。
第一组查询：Jon和Gunnar，Gunnar的父亲就是Jon。这意味着Jon是Gunnar的直系父亲，共同祖先Jon到两人距离分别为0和1，都小于5，所以输出No。
第二组查询：Jon和Rurik。Jon的父亲Arnar，Arnar的父亲Rurik，所以Rurik是Jon的祖父，距离为2。到Rurik自己距离为0，都小于5，输出No。
程序运行结果和我手工推的一致。再用一组超过五代的查询，比如让Rurik是某人的第6代祖先，程序会输出Yes，说明边界没有被扩大。
4.2 我踩过的三个坑
第一个坑：查询行只读了两个token。一开始我把查询行当成“名 姓”两组，直接读两个nextToken()，结果第二组人的名字全被姓顶替，导致判断完全错误。后来改成四个token，跳过第二和第四个，问题立刻消失。
第二个坑：父名未知时往map里放了空字符串。substring截出来如果是空串，father.put(name, "")之后，father.get(空串)虽然返回null，但cur会变成空串，然后空串进入比较逻辑。最要命的是，不同人的空串可能被误认为同一个祖先，造成错误。所以要加一个parent.length() > 0的判断。
第三个坑：输出用System.out.println。在M可能上万甚至十万的情况下，频繁调用println会消耗大量时间。改成StringBuilder后，时间下降明显。PTA对Java的时限本来就不是很宽松，这种常数级优化必须做。
4.3 为什么这个写法不会超时
先看复杂度。读入N个人，每个人做一次字符串endsWith和substring，加上HashMap的put，总复杂度是O(N)。每查询一次，最多取5个节点，B最多检查5个节点，每个节点做最多5次字符串equals，也就是常数25次比较。如果M是100000，总的比较次数也就是250万级别，这对Java来说完全在安全线以内。
真正需要担心的是祖先链特别长时，如果采用“把整条链都存进List”的做法，一次查询可能要遍历几百个节点，再叠加HashMap查找，数量级会差很多。而我们把深度硬限制为5，等于把每次查询的耗时压成了一个极小的常数。
还有一个细节：HashMap的get方法是O(1)的，但字符串哈希也需要计算。不过这里反复使用的key都是已经存在的String对象，哈希值在String内部有缓存（第一次计算后缓存），所以实际性能比想象中好。这也是为什么用String作为key而不是用自定义对象的主要原因。
5. 从这道题往外扩一步
5.1 如果题目改成“任意代以内”怎么处理
有些变种题会要求判断两个人是否有任意共同祖先，而不限制代数。此时只存5个节点就不够了，得把两个人的完整祖先链都收集起来，再用一个HashSet做交集。
思路是：从A开始不断father.get(A)直到null，把路径上所有节点放进一个HashSet；再从B开始不断向上走，第一个出现在HashSet里的节点就是最近公共祖先。找到之后，还能顺便算出公共祖先到两个人的距离。
这个变种更接近“LCA最近公共祖先”的经典题型。理解了L2-030的“只查五代”，也就理解了为什么LCA要限制深度：因为题目只需要局部信息，不需要全局信息。
5.2 反向建“子女列表”能解决什么问题
如果题目再进一步，要求输出两个人之间的具体关系，比如“祖父”“外祖父”“表兄弟”等，那么单一的父指针map就不够用了。我们可以额外维护一个Map<String, List<String>> children，父亲的key对应子女列表，从祖先向下做BFS，找到目标人并记录深度。
不过那是另一道题了。L2-030保持简单：只存父亲、只查五代、只输出Yes/No。能把简单问题做对，有时候比强行把问题复杂化更重要。
6. 最后分享一点我的实操体会
刷这道题让我最意外的是，“五代以内”的边界定义居然会同时影响正确性和性能。刚开始我用的是while (i < 6)，不仅多算了一代，还隐隐担心数据量会不会很大；改成i < 5之后，测试点全绿，运行时间也降了一点。这说明读题时真的要把“代数”和“边数”换算清楚，代码里少一行循环，背后是对题意的精准理解。
另外，PTA上用Java交题，千万别迷信什么高级优化技巧。BufferedReader+StringBuilder+ 常数级算法，这三板斧足以解决绝大多数L2级别的题目。冰岛人这道题如果你也卡在超时上，不妨先检查一下是不是用了Scanner，或者查询行少读了两个token。
最后再给一个小建议：自己本地多构造几组带“超过五代”的测试数据跑一遍。这类边界用例往往比官方样例更能暴露问题。把父名未知、空串、目标祖先在第五层边界这些情况全部试一遍，你的代码就能安心交上去了。
