家谱(gen)

形式化题目

给定一个由多组父子关系组成的家谱，包含若干次查询。家谱用如下指令描述，每个指令由一个字符加名字组成：

#name：把「当前父亲指针」设置为 name。name 若是新名字则自立为根；如果 name 已经存在，则仅将当前父亲指针指向他。
+name：声明 name 是当前父亲的儿子。
?name：查询 name 的最早祖先。
$：输入结束标志。

保证：

每个人名字长度为 $6$ ，且首字母大写，没有重名。
每个查询操作输出一行，格式为：被查询人的名字 + 一个空格 + 最早祖先的名字。

正解

思路

这是一个典型的**并查集（Disjoint Set Union）**应用题。题目要求“最早的祖先”，也就是不断向上追溯父亲节点，直到没有父亲的节点为止，这恰好对应了并查集中查找集合代表元（根节点）的操作。因为存在边修改结构边查询的操作，所以查询必须是“在线”的，即根据到目前为止已经建立的关系回答查询，而不是读完全部数据再统一回答。

由于人物的名字为字符串，可以使用哈希表或二叉搜索树（如 C++ 中的 std::map<string, string> 或 Python 中的 dict）来充当并查集的底层 parent 数组。

当遇到 #name 时，我们只需把一个全局/局部变量 current_father 设为 name。如果 name 是第一次出现，将他在并查集中的祖先设为自己。
当遇到 +name 时，相当于得知 name 是 current_father 的儿子。在并查集中，这对应一个合并操作：将 name 所在家族的根挂到 current_father 所在家族的根下。
当遇到 ?name 时，只需查询 name 的根节点并输出。

关于路径压缩 使用并查集查找代表元时，引入路径压缩可以使得单次查询和合并的均摊复杂度极低。虽然对于小深度树不加也能过，但这是一种保证代码鲁棒性的核心技巧。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 20:09
# update_at: 2026-10-08 20:09

import sys
from collections.abc import Iterator

type Parents = dict[str, str]  # 人名 -> 父亲，根节点指向自己；名字是字符串，故用 dict 充当并查集底数组

FATHER_MARK = '#'   # 声明「当前父亲」：其后连续的 '+' 都挂在他名下
SON_MARK = '+'      # 认领一个儿子
QUERY_MARK = '?'    # 查询某人的最早祖先
END_MARK = '$'      # 输入结束


def find_root(parents: Parents, name: str) -> str:
    """返回 name 的最早祖先，并压缩路径：把沿途节点直接挂到祖先下。

    用迭代而非递归：数据里的家谱链可长达上万代（GEN8/GEN9），递归会爆栈。
    """
    path: list[str] = []
    while parents.get(name, name) != name:  # 沿父亲方向上溯，记下待压缩的节点
        path.append(name)
        name = parents[name]
    for node in path:                       # 回填：途经节点全部直连根，缩短后续查询
        parents[node] = name
    return name


def run_instructions(tokens: Iterator[str]) -> list[str]:
    """顺序执行指令流，返回每个 '?' 的「本人 最早祖先」答案。"""
    parents: Parents = {}
    current_father = ''
    answers: list[str] = []

    for token in tokens:
        if token == END_MARK:
            break
        op, name = token[0], token[1:]
        if op == FATHER_MARK:
            current_father = name
            parents.setdefault(name, name)          # 新名字先自立为根
        elif op == SON_MARK:
            child_root = find_root(parents, name)
            father_root = find_root(parents, current_father)
            parents[child_root] = father_root       # 整棵子树接到父亲家族的根下
        elif op == QUERY_MARK:
            answers.append(f'{name} {find_root(parents, name)}')

    return answers


def solve() -> None:
    # 按 token 读、不按行读：数据文件是 CRLF 行尾，split() 一并吃掉 '\r' 与空行
    tokens = iter(sys.stdin.read().split())
    answers = run_instructions(tokens)
    sys.stdout.write('\n'.join(answers) + ('\n' if answers else ''))


if __name__ == '__main__':
    solve()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 20:09
 * update_at: 2026-10-08 20:09
 */
#include <iostream>
#include <string>
#include <map>

using namespace std;

typedef long long ll;

// 并查集底层：人名 -> 代表元。代表元沿父亲方向上溯，
// 根（代表元就是自己）即该家族最早的那位祖先。
// 用 map<string,string> 代替数组，等价于把字符串名字当作下标。
map<string, string> parent_map;

// 返回 name 的最早祖先，并把沿途节点直接挂到祖先后（路径压缩）。
string find_root(const string &name) {
    auto it = parent_map.find(name);
    if (it == parent_map.end()) {   // 第一次出现的人，自己就是家族根
        parent_map[name] = name;
        return name;
    }
    if (it->second == name) {       // 已经指向自己，说明是根
        return name;
    }
    parent_map[name] = find_root(it->second);
    return parent_map[name];
}

// 把 child 所在家族整体接到 father 所在家族之下
void add_son(const string &child, const string &father) {
    string child_root = find_root(child);
    string father_root = find_root(father);
    if (child_root != father_root) {
        parent_map[child_root] = father_root;
    }
}

// 单组数据：顺序执行指令直到 '$'
void solve() {
    string str;
    string current_father;      // 最近一个 '#name' 声明的父亲，随后的 '+name' 都挂在他下面
    while (cin >> str) {
        if (str == "$") {
            break;
        }
        char op = str[0];
        string name = str.substr(1);

        if (op == '#') {
            current_father = name;
            if (parent_map.find(name) == parent_map.end()) {
                parent_map[name] = name;    // 新名字先自立为根，日后被 '+name' 认领时会改指
            }
        } else if (op == '+') {
            add_son(name, current_father);
        } else if (op == '?') {
            cout << name << " " << find_root(name) << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

复杂度

时间复杂度：令 $n$ 为总人数、 $q$ 为指令总数。每次使用 std::map 查找字符串时间为 $O(L \log n)$ （ $L=6$ 为字符串长度）。并查集的路径压缩带来阿克曼函数反函数的常数时间 $\alpha(n)$ 。总时间复杂度近似为 $O((n + q) \log n)$ 。对于 Python 而言，由于字典为哈希表实现，时间复杂度可近似视为 $O((n + q) \cdot \alpha(n))$ 。两者均能轻松通过。
空间复杂度：需要存储至多 $n$ 个字符串及其父亲的映射，空间复杂度为 $O(n \times L)$ ，满足要求。

总结

本题中需要特别注意以下几点坑和细节：

四种指令的具体语义 尤其是 #name，它的含义是把「当前父亲指针」置为 name，而不是“新开一个家族的根”。name 完全可能是之前已经被当作儿子加入的成员，此时他依然有自己的父亲。样例中：
text
```
1
2
3
4
5#Arthur      ← 设当前父亲 = Arthur
+Gareth      ← Gareth 的父 = Arthur
+Walter      ← Walter 的父 = Arthur   ← 连续两个 + 都挂在同一个当前父亲下
#Gareth      ← 设当前父亲 = Gareth（Gareth 已有父！）
+Edward      ← Edward 的父 = Gareth
```
在后台的大数据点中，多次出现这样的重绑定。必须准确理解，否则会大量 WA。
题面规模声明与真实数据严重不符 题面声称“最多 1000 组父子关系”、“家谱不超过 30 代”。但在实际数据中，测试点 GEN8 和 GEN9 包含多达 20000 组父子关系，构成的树深度高达 10000 代。这导致：
- 依赖“链条深度小所以无需路径压缩”的结论是不可靠的。虽然在当前数据集中查询集中在链的顶端，不压缩也能跑，但面对 10000 代的树，进行路径压缩是应有之义。
- 既然深度达到上万层，如果使用递归实现并查集的 find_root，极易在某些语言/环境下爆栈。因此，将 find_root 写为迭代加回填（如 Python 实现中那样）是更稳妥的做法。
输入解析的细节 按行处理时可能会被行末可能存在的连续空格、回车符（CRLF）或空行干扰。直接按词法 token 逐个读取（例如 C++ 的 cin >> str，Python 的 sys.stdin.read().split()）可以有效规避这些问题。遇到 $ 后应立刻跳出读取循环。
在线回答 题目是按指令输入顺序进行输出的。处理到 ? 时只能利用当前已知的父子关系。所以查询不能留到读完所有指令之后再统一处理。

目录

形式化题目

正解

思路

代码

复杂度

总结