说实话第一次在洛谷看到 P14259「兄妹siblings」这个题名的时候我下意识觉得这题肯定是个树上 LCA 或者并查集的高级货毕竟“siblings”在算法题里总是容易往家族关系、树上祖先那一类方向靠。结果把题面读完才发现它考的其实是一个非常朴素的关系判断模型解决“两个人是不是同一个爸妈生的”这个问题。这篇文章就按照我做题时的完整思路来写从题面抽象、算法选型到最终代码实现再附上一些我踩过的坑和题目变式希望对正在刷关系类模拟题的你有帮助。1. 题面解读先搞清楚“兄妹”到底在判什么1.1 题目要求我们回答什么抛开故事背景P14259 的“兄妹”关系落在算法层面通常可以归结为给定若干条“谁是谁的父亲/母亲”的关系再给出一组询问每次问两个节点是否互为兄弟姐妹。兄弟姐妹的判定标准也很直白——它们必须拥有至少一个共同的父节点或共同的母节点而且这两个节点本身不能是同一个个体。这里有一个很容易被忽略的细节“兄妹”这个词在中文语境里更多强调“同父同母”但在英文原题的 siblings 里同父异母、同母异父也算是广义上的 siblings。所以拿到题第一步不是急着写代码而是去题面里确认它到底要求“同父即可”还是“同父且同母”这直接决定了你要不要增加一个 mother 数组。我在这次题解里按更严格的“同父即 siblings”来拆解因为这是大多数关系判断题的通用最小模型如果题目额外要求同母只需要把同样的判断逻辑再套一层即可。1.2 把自然语言翻译成数据结构这类题的典型输入形式是第一行给你节点总数 n、关系边数 m 和询问次数 q接下来 m 行每行给出一条关系比如 a b 表示 a 是 b 的父亲最后 q 行是若干对询问 (u, v)。我们需要回答每一对询问中的 u 和 v 是否满足“兄妹”条件。把这种带有人物角色的数据扔进程序里最自然的方式就是数组映射用 fa[i] 记录节点 i 的父亲是谁。如果 fa[u] 和 fa[v] 的值非零且相等说明 u 和 v 在同一父亲名下答案就是 YES否则就是 NO。注意这里我特意强调“非零”因为在大多数题目里节点编号从 1 开始0 被保留用来表示“这个节点没有给出父节点信息”。如果你没有处理根节点或孤儿节点的 fa 为 0 的情况一上来直接比较 fa[u] fa[v]两个根节点的 fa 都是 0就会错误地把两个没有关系的祖先节点判成兄妹这一条几乎是我见过最多人翻车的原因后面第 4 节我会专门展开讲。2. 算法骨架从朴素模拟到 O(1) 查询2.1 最直接的方案数组标记法如果关系网络是“每个节点最多只有一个父亲”的树状或森林结构那么判断两个节点是否为兄妹本质上就是比较两个节点的直接父节点是否相同时间复杂度是 O(1) 的。整体流程可以拆成三步读入 n, m, q并初始化 fa 数组全部置为 0或者 -1读入 m 条父子关系更新 fa[child] father对于每个询问比较 fa[u] 与 fa[v]输出对应答案。有人可能会问这题真的就这么简单吗其实大多数洛谷的“关系模拟题”核心就是这一步。你不需要建图不需要跑 DFS更不需要上 LCA因为题目只问“直接父亲是否相同”并没有问你“最近公共祖先是谁”。如果把问题扩大到“判断两个节点是否有同一个祖父”那才轮到 LCA 出场那是另一种题。2.2 节点是字符串怎么办哈希映射有的变式题不会好心地给你整数编号输入里全是人名比如 Tom Jerry那就得先做人名到编号的映射。最省事的做法是 unordered_mapstring, int id每个人名第一次出现时就分配一个新编号。这一步有一点值得注意如果你使用 mapstring, int红黑树实现单次查找是 O(logn) 的在 n 达到 10^5 级别时其实也能过但会明显慢于 unordered_map 的 O(1) 平均查找。当然 unordered_map 在遭遇恶意构造的哈希碰撞时可能退化但洛谷的字符串关系题一般不会刻意卡这个实测用它是最平衡的选择。还有一个细节字符串大小写是否敏感、是否可能出现一个人名既是父亲又是儿子这些都要在写映射时考虑。我的习惯是读取后立刻统一转成小写再判断省得后面因为大小写问题 WA 得莫名其妙。2.3 能不能用并查集这里是个大坑我在初学阶段遇到“判断两人是否属于同一家庭”这类题总想用并查集去合并。并查集在“判断两个节点是否在同一棵树/同一个连通分量”里确实很合适但放到 P14259 的“兄妹”判定里就出问题了。因为并查集维护的是“传递的等价关系”一旦 a 和 b 是兄弟b 和 c 是父子并查集很可能把 a 和 c 也划到同一个集合里但 a 和 c 并不是 siblings。换句话说并查集会把你导到“两人是否有亲戚关系”这个更大的概念上去而不是题目要求的“两人的直接父亲是否相同”。所以我在题解里给一个明确结论如果题面只要求判断“同父的兄妹”不要用并查集老老实实用 fa 数组做直接父节点比较。并查集不是不行而是用在这里需要额外维护每个父亲的儿子集合复杂度和代码量都上去了收益却不明显。2.4 复杂度对比与选型建议为了让你对不同方案的适用范围有直观认识我把三种常见方案的复杂度列一张表方案预处理复杂度单次询问复杂度适用场景fa 数组直接比较O(m)O(1)节点是整数编号、每个节点最多一个父亲unordered_map 映射后比较O(m)O(1)节点是人名等字符串形式并查集 额外维护O(m α(n))O(α(n))需要判断“是否同一家族”而非“同父”从表里能明显看出fa 数组方案在绝大多数情况下都是最优解。只有当题目场景变成“判断属于同一个大家族”时并查集才真正有用武之地。做题先读清题意不要因为题目名字带“关系”两个字就默认是图论难题。3. 完整实现C 代码与关键细节拆解3.1 数据定义与读入过程先说我的代码设计。为了兼容“判断同父即可”和“需要判断同母”两种模式我直接用两个数组 fa 和 ma如果题目只用到父亲信息ma 数组建了也不影响正确性就当给后续扩展留了余地。我用 vector 而非原生数组一方面是不用担心 n 的边界问题另一方面初始化所有值为 0 也非常方便。读入这一块我强烈建议用 scanf 而不是 cin尤其是 q 和 m 都能到 10^5 以上的题。你用 cin 加 ios::sync_with_stdio(false) 也能过但我个人实测下来在洛谷这类 OJ 上快读有时候能帮你避开非确定性 TLE 的尴尬。下面这段是核心读入逻辑#include bits/stdc.h using namespace std; const int MAXN 100005; int fa[MAXN], ma[MAXN]; int main() { int n, m, q; scanf(%d%d%d, n, m, q); // 初始化-1 表示该节点的父/母信息未知 memset(fa, -1, sizeof(fa)); memset(ma, -1, sizeof(ma)); for (int i 0; i m; i) { int rel, a, b; scanf(%d%d%d, rel, a, b); if (rel 0) fa[b] a; // a 是 b 的父亲 else ma[b] a; // a 是 b 的母亲 } // 询问部分见后文 return 0; }这里的 rel 字段是我假设题面会在关系类型里区分父子/母子如果原题直接只有一种父子关系你直接把 rel 和 ma 相关部分去掉就行结构是完全一致的。3.2 核心判断逻辑的三种写法判断逻辑本身很简单核心就是比较 fa[u] 和 fa[v]以及 ma[u] 和 ma[v]。但“怎么判断才准确”是有讲究的我写三个递进版本给你看。版本一只比较 fa 相等与否if (fa[u] fa[v]) puts(YES); else puts(NO);这个版本的问题是没排除“两人都是根节点”的情况。如果 u 和 v 都是没有父亲信息的孤立点fa[u] 和 fa[v] 同时等于 -1输出 YES 就是错误的。因此必须加一个前提至少有一个人的父节点信息是有效的。版本二排除无效节点的比较bool isSibling(int u, int v) { if (u v) return false; // 自己不是自己的兄妹 if (fa[u] -1 || fa[v] -1) return false; // 有人的父亲未知 return fa[u] fa[v]; }这个版本已经能应对绝大多数情况。这里 fa[u] -1 的检查非常关键它把根节点、孤儿节点全部挡在外面。u v 的判断也要保留题目几乎一定会隐藏这个边界用例。版本三同父同母的严格模式bool isFullSibling(int u, int v) { if (u v) return false; if (fa[u] -1 || fa[v] -1) return false; if (ma[u] -1 || ma[v] -1) return false; return fa[u] fa[v] ma[u] ma[v]; }如果原题描述里强调“兄妹必须同父同母”那就用版本三。面试或比赛里经常出现版本二和版本三的区别这也是一个容易被测试用例卡住的地方。3.3 完整可运行的参考代码下面给出一份可以在本地直接编译运行的完整参考代码我以“同父即视为兄妹”为默认规则并保留 ma 数组以备扩展#include bits/stdc.h using namespace std; const int MAXN 100005; int fa[MAXN], ma[MAXN]; bool isSibling(int u, int v) { if (u v) return false; if (fa[u] -1 || fa[v] -1) return false; return fa[u] fa[v]; } int main() { int n, m, q; scanf(%d%d%d, n, m, q); memset(fa, -1, sizeof(fa)); memset(ma, -1, sizeof(ma)); for (int i 0; i m; i) { int rel, a, b; scanf(%d%d%d, rel, a, b); if (rel 0) fa[b] a; else ma[b] a; } while (q--) { int u, v; scanf(%d%d, u, v); puts(isSibling(u, v) ? YES : NO); } return 0; }这份代码的复杂度是 O(m q)预处理 O(m)每次询问 O(1)内存占用只有两个长度 n 的 int 数组在 10^5 级别的数据下完全没有任何压力。你直接在洛谷的代码框里提交把流同步关闭和快读补上基本能跑进几十毫秒。4. 踩坑实录与常见问题排查4.1 第 1 坑编号从 0 开始还是从 1 开始很多关系题为了制造障碍会把节点编号设置为从 0 开始。如果题目说“人名编号范围为 0 到 n-1”你却开了大小 n 的数组确实也不会越界但 memset 后的默认初始化值可能恰好和某个合法节点编号重合导致误判。我的建议是无论题目编号从几开始都把 fa 的无效值设为 -1这样就能彻底避开“0 到底是不是有效节点”的纠缠。这个习惯帮我省了很多次 DEBUG 时间。4.2 第 2 坑根节点和孤立节点怎么处理这个问题在第 2 节提过一次但因为实在是太高频我还是要单独拉出来说。fa[u] -1 并不代表“u 不存在”而是代表“u 的父亲信息没有给出”。此时 u 可能是某棵关系树的根也可能完全是一个孤立点。如果你跳过这个判断那所有根节点之间都会被误判为兄妹如果你把 fa[u] -1 当成“无解”直接输出 NO又可能漏掉“根节点的两个孩子”这种情况。所以比较前必须做双重检查既检查 fa[u] 和 fa[v] 都非 -1再比较两者是否相等。4.3 第 3 坑自己算不算自己的兄妹题目如果没特别说明u 和 v 相等时通常应该输出 NO因为一个人不能是自己的 siblings。这个用例非常隐蔽很多 AC 代码都在这里栽过跟头。但也要留个心眼万一题面定义“每个个体都是自己的兄弟姐妹”那就得按题面来。比赛里不确定的时候看样例样例没给就按常识输出 NO。4.4 大数据输入的读入优化当 m 和 q 到达 10^5 甚至 10^6 时cin 的默认同步模式会带来显著性能损耗。我建议直接使用 scanf或者在最前面加上ios::sync_with_stdio(false); cin.tie(0);再配合 cin 使用。如果你还想追求极限可以手写 getchar 快读但对于 P14259 这个级别scanf 完全够用没必要为了炫技增加代码出错概率。4.5 常见问题速查表症状可能原因解决办法全 YES 或全 NO默认值初始化成 0根节点被误判把 fa 初始化为 -1数据一大就超时用了 cin 且未关闭流同步改用 scanf 或添加 ios 同步关闭字符串人名全部错乱未建映射或映射顺序错误使用 unordered_map 统一编号边界用例 WA没判断 u v比较前增加自身排除逻辑关系关系全部错位父子关系方向存反确认是 fa[b] a 还是 fa[a] b调试小技巧自己写一个对拍器随机生成小规模关系数据用暴力解法每对节点查一遍关系链和你的优化解法对拍是目前效率最高的查错方式。不要只看洛谷报的 WA 用例数据规模一大人工根本看不出来。5. 题目变式与扩展把 P14259 的思路迁移到更多场景5.1 变式一统计一个家庭里的兄妹对数量洛谷经常把简单关系题包装成计数题问你“所有兄妹对共有多少对”。如果一个父亲有 cnt 个孩子那这个家庭内部的兄妹对数量就是 C(cnt, 2)也就是 cnt × (cnt - 1) / 2。实现上只需要在读入关系时顺便维护一个 sonCnt[father] 计数器最后遍历所有父亲节点把所有 C(cnt, 2) 累加起来即可。这种变式看着只是从“判断”变成“计数”但有个细节一个节点可能同时出现在多个关系里如果题目构建的是一棵多叉树而不是森林那么每个节点只有一个父亲这个计数不会重复但如果数据里允许一个节点有多个父亲即图而不是树计数之前需要去重否则就会把同一个兄妹对算多次。5.2 变式二判断“同祖父”或更远的祖先关系如果题面把 siblings 扩展成“同祖父”那就不能只看 fa 数组了。你需要先预处理出 grandpa[i] fa[fa[i]]然后在判断时比较 grandpa[u] 和 grandpa[v]。这个思路可以一直套下去比如“同曾祖父”“同高祖父”。但层数一旦变多预处理和存储都会变得昂贵而且和 LCA 的某些场景开始重合届时就需要考虑倍增法了。我记得有一道区域赛题就是把“兄弟节点”的判断扩展到了“堂兄弟节点”当时我第一反应还是 fa 数组硬写结果层数一多就不行了。后来才意识到这种“先找共同的第 k 级祖先再比较其子节点”的问题本质上是 LCA 的变体。所以我的建议是先问自己“k 是不是固定的”k 固定就预处理好第 k 级祖先数组k 不固定再用倍增或树上差分。5.3 变式三用姓氏字符串判断家族归属在实际工程场景里节点名往往是姓名字符串比如“ZhangSan”和“ZhangSi”而“兄妹”关系可能被包装成“判断两人是否来自同一个家族同一个姓氏”。这种情况下算法核心从“比较直接父亲”变成了“比较姓氏前缀”你需要对字符串做前缀提取然后建立哈希映射。我在处理这类题时习惯把姓氏提取作为单独函数抽出来方便对拍和调试。5.4 小结关系类题目的通用套路刷多了 P14259 这类关系题后我总结出一个很直白的套路。第一步永远是把题面里的人名、关系、判断条件翻译成“谁指向谁”的数组结构第二步是明确判断条件到底是“一层关系”“两层关系”还是“任意层关系”一层用 fa 数组两层用 grandpa 数组或 LCA任意层直接上倍增和树上算法第三步才是考虑数据范围、读入优化和字符串哈希这些外围工程问题。这个顺序不能颠倒。很多人一看到“兄妹”就默认是并查集题一看到“树上关系”就默认是 LCA 题结果把简单题做复杂还怎么调都调不对。关系题的难点往往不在算法本身而在你对题意的抽象是否精确。最后再分享一个实战小技巧遇到这种名字带迷惑性的题先把样例输入手动画成一张小图用肉眼模拟一遍答案再拿你的程序跑一遍。这个过程能同时验证两件事——你对题面的理解是否正确以及你的代码逻辑是否跟你的理解一致。我在 P14259 上基本没走弯路靠的也是先画图再写码这个习惯。希望这篇题解能帮你把这题的思路彻底理顺顺便把关系类模拟题的通用解法也一并掌握。