家谱 - 题目列表

题意

输入按行描述家谱：#name 切换当前父亲，随后的 +child 表示这个孩子的父亲是当前父亲；?name 查询此人的最早祖先，$ 结束。

思路

用字典 parent[name] 记录每个人的直接父亲。没有更早祖先的人令 parent[name]=name。

查询时沿着父亲指针一直走到 parent[name]==name，该名字就是最早祖先。把途中人物都直接指向这个祖先，即路径压缩，后续查询会更快。

处理 #name 时只能使用 setdefault：一个人可能此前作为 +child 已经记录了父亲，后来又成为另一组父子关系的父亲，不能把他错误重置为自己的根。样例中的 Gareth 就属于这种情况。

Python 知识

Python 字典可以直接用姓名字符串或 bytes 作键，不需要先给每个名字编号。
setdefault(name,name) 只在姓名首次出现时初始化，不覆盖已有父子关系。
line[:1] 取操作符，line[1:].strip() 取姓名，适合解析这种无空格的命令行。
用 path 列表记录查询途中的人物，再统一路径压缩，避免递归。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：逐行读取和字符串切片。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：字典映射模式。

代码

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
36import sys


def main():
    parent = {}
    current_parent = None
    answer = []

    def find(name):
        parent.setdefault(name, name)
        path = []
        while parent[name] != name:
            path.append(name)
            name = parent[name]
        for person in path:
            parent[person] = name
        return name

    for line in sys.stdin.buffer:
        operation = line[:1]
        if operation == b"$":
            break
        name = line[1:].strip()
        if operation == b"#":
            current_parent = name
            parent.setdefault(name, name)
        elif operation == b"+":
            parent[name] = current_parent
        else:
            answer.append(name.decode() + " " + find(name).decode())

    print("\n".join(answer))


if __name__ == "__main__":
    main()

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/**
 * P2814 家谱
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;
const int MOD = 50021;

// 哈希表：名字 → 父结点指针（编号）
struct Entry {
    char name[12]; // 原名字，用于输出
    int parent;    // 父结点在 tbl 中的下标，自己指向自己即为根
    int next;      // 哈希链表
} tbl[MAXN];
int head[MOD], cnt;

// 简单的字符串哈希
int hash_str(const char *s) {
    unsigned int h = 0;
    for (int i = 0; s[i]; ++i)
        h = h * 131 + s[i];
    return h % MOD;
}

int get_or_create(const char *s) {
    int hv = hash_str(s);
    for (int i = head[hv]; i; i = tbl[i].next)
        if (!strcmp(tbl[i].name, s)) return i;
    ++cnt;
    strcpy(tbl[cnt].name, s);
    tbl[cnt].parent = cnt; // 初始指向自己
    tbl[cnt].next = head[hv];
    head[hv] = cnt;
    return cnt;
}

// 找祖先（带路径压缩）
int find(int x) {
    if (tbl[x].parent != x)
        tbl[x].parent = find(tbl[x].parent);
    return tbl[x].parent;
}

int main() {
    char line[20];
    int cur = 0;
    while (scanf("%s", line) == 1) {
        if (line[0] == '$') break;
        int id = get_or_create(line + 1);
        if (line[0] == '#') {
            cur = id;
        } else if (line[0] == '+') {
            tbl[id].parent = cur;
        } else { // '?'
            int root = find(id);
            printf("%s %s\n", line + 1, tbl[root].name);
        }
    }
    return 0;
}

复杂度

设关系与查询总数为 q。路径压缩后总时间接近 $O(q\alpha(q))$ ，字典和父链占用 $O(q)$ 空间。

总结

这题的父子关系天然就是“姓名指向父亲”的映射。setdefault 保留旧父亲信息、路径压缩加速重复查询，是 Python 实现中最值得注意的两点。

家谱

目录

题意

思路

Python 知识

代码

复杂度

总结