皇室夫人名字前缀统计题解

题目分析

这个问题要求统计皇室家族中所有夫人的名字以给定字符串为前缀的数量。皇室家族的关系构成一棵树，其中：

• 1号夫人是根节点，名字只有一个字母
• 其他夫人的名字 = 自己的首字母 + 母亲的名字

我们需要高效处理大规模数据（n, k ≤ 10^6），因此需要一个O(n)或O(n log n)的算法。

关键思路

1. 树形结构：皇室家族关系形成一棵树，每个节点的名字由其首字母和母亲的名字连接而成
2. Trie数据结构：使用字典树存储所有夫人的名字，可以高效进行前缀查询
3. DFS构建：通过深度优先搜索遍历家族树，构建每个夫人的完整名字并插入Trie

算法步骤

1. 构建家族树：读取输入数据，建立父子关系
2. DFS遍历：从根节点开始DFS，构建每个夫人的完整名字
3. Trie插入：在DFS过程中将每个夫人的名字插入Trie
4. 查询处理：对于每个查询字符串，在Trie中查找前缀匹配的数量

时间复杂度

• 构建Trie：O(总名字长度)
• 每次查询：O(查询字符串长度)
• 总体复杂度：O(n + k)，能够处理10^6规模的数据

C++实现

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1000000;
const int ALPHABET = 26;

struct TrieNode {
    int count;
    int children[ALPHABET];
    
    TrieNode() {
        count = 0;
        memset(children, -1, sizeof(children));
    }
};

class Trie {
private:
    vector<TrieNode> nodes;
    
public:
    Trie() {
        nodes.push_back(TrieNode());
    }
    
    void insert(const string& s) {
        int node = 0;
        for (char c : s) {
            int idx = c - 'A';
            if (nodes[node].children[idx] == -1) {
                nodes[node].children[idx] = nodes.size();
                nodes.push_back(TrieNode());
            }
            node = nodes[node].children[idx];
            nodes[node].count++;
        }
    }
    
    int query(const string& s) {
        int node = 0;
        for (char c : s) {
            int idx = c - 'A';
            if (nodes[node].children[idx] == -1) {
                return 0;
            }
            node = nodes[node].children[idx];
        }
        return nodes[node].count;
    }
};

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    vector<char> firstChar(n + 1);
    vector<int> parent(n + 1);
    vector<vector<int>> children(n + 1);
    
    // 读取输入并构建树结构
    for (int i = 1; i <= n; i++) {
        char c;
        int p;
        scanf(" %c %d", &c, &p);
        firstChar[i] = c;
        parent[i] = p;
        if (p != 0) {
            children[p].push_back(i);
        }
    }
    
    Trie trie;
    
    // 使用DFS构建所有名字
    vector<pair<int, string>> stack;
    stack.push_back({1, string(1, firstChar[1])});
    
    while (!stack.empty()) {
        auto [node, name] = stack.back();
        stack.pop_back();
        
        trie.insert(name);
        
        for (int child : children[node]) {
            stack.push_back({child, firstChar[child] + name});
        }
    }
    
    // 处理查询
    for (int i = 0; i < k; i++) {
        char s[1000001];
        scanf("%s", s);
        printf("%d\n", trie.query(string(s)));
    }
    
    return 0;
}

样例分析

对于题目中的样例：

• 皇室家族有10位夫人
• 查询"RY"：有2位夫人的名字以"RY"开头（RYS和RYAENERYS）
• 查询"E"：有2位夫人（ERYS和ENERYS）
• 查询"N"：有1位夫人（NERYS）
• 查询"S"：有1位夫人（S）
• 查询"AY"：没有夫人以"AY"开头

优化技巧

1. 避免字符串连接：在DFS过程中使用字符串连接可能较慢，可以改用字符数组和索引
2. 内存管理：预分配Trie节点空间以减少动态分配开销
3. 输入输出优化：使用scanf/printf代替cin/cout提高IO效率

这个解决方案能够高效处理大规模输入，满足题目要求。