你好！作为金牌教练，我非常高兴看到你已经在掌握基础 Trie 树后，开始挑战 Trie 树的动态维护与频率统计。

在 NOI 竞赛中，这被称为“带权字典树”或“可删字典树”。相比基础版，它引入了路径权值和动态删除的概念。在 LeetCode 上这叫“Implement Trie II”，在竞赛中，这是处理字符串集合中“出现次数”和“前缀频数”的标准做法。

题目名称：Implement Trie II (Prefix Tree)

题目描述

请你实现一个能够支持动态增删及频率统计的前缀树（Trie）。该树需要支持以下四个功能：

1. insert(word): 向 Trie 中插入字符串 word。
2. countWordsEqualTo(word): 返回 Trie 中字符串 word 出现的次数。
3. countWordsStartingWith(prefix): 返回 Trie 中以 prefix 为前缀的字符串的总数量。
4. erase(word): 从 Trie 中删除一个字符串 word。题目保证在调用此接口时，word 至少存在于 Trie 中一次。

输入格式

第一行包含一个整数 $Q$，表示操作的总次数。 接下来的 $Q$ 行，每行包含一个操作命令及相应的参数。 命令包括：Trie, insert, countWordsEqualTo, countWordsStartingWith, erase。

输出格式

对于每一个操作，输出一行。

• Trie、insert、erase 操作输出 null。
• countWordsEqualTo、countWordsStartingWith 操作输出对应的整数。

样例数据

输入：

10
Trie
insert apple
insert apple
countWordsEqualTo apple
countWordsStartingWith app
erase apple
countWordsEqualTo apple
countWordsStartingWith app
erase apple
countWordsStartingWith app

输出：

null
null
null
2
2
null
1
1
null
0

数据规模说明

• $1 \le Q \le 5 \times 10^4$
• 字符串总长度不超过 $10^5$。
• 所有字符均为小写英文字母。
• 内存提示：NOI 竞赛中，建议使用静态数组 trie[MAXN][26]。本题需要额外维护两个计数数组：pass_cnt[MAXN]（经过该节点的单词数）和 end_cnt[MAXN]（以此节点结尾的单词数）。

预备知识点

1. 路径权值维护：每次 insert 时，路径上经过的所有节点的 pass_cnt 加 1。
2. 终点权值维护：在单词结束位置，end_cnt 加 1。
3. 动态删除：erase 是 insert 的逆过程，路径节点 pass_cnt 减 1，终点 end_cnt 减 1。
4. 前缀频数：countWordsStartingWith 的结果即为前缀最后一个字母所在节点的 pass_cnt 值。

启发式思路引导（草稿纸推理）

1. 节点状态的演变：
   • 想象你在每个房间（节点）放了两个计数器：一个门口的计数器（pass_cnt），一个屋子中央的计数器（end_cnt）。
   • 插入 "apple"：经过 'a', 'p', 'p', 'l', 'e' 的房间，门口计数器全部加 1，最后在 'e' 房间中央计数器加 1。
2. 删除的逻辑：
   • 删除 "apple"：原样走一遍，所有门口计数器减 1，'e' 房间中央计数器减 1。
   • 思考：在竞赛中，我们通常不需要真正销毁数组空间，只要计数器归零，在逻辑上这个单词就消失了。
3. 查询的差异：
   • 查“有多少个 apple”：看 'e' 房间中央的计数器。
   • 查“有多少个以 app 开头”：看第二个 'p' 房间门口的计数器。

核心逻辑流程图（伪代码提示）

1. 插入 (Insert) 与 删除 (Erase)

graph TD
    Start("开始: insert 或 erase word") --> Init("p = 0 (根节点)")
    Init --> Loop{"遍历字符 c"}
    Loop -- "还有字符" --> GetID("id = c 减去 'a'")
    GetID --> CheckExist{"insert 且节点不存在?"}
    CheckExist -- "是" --> Create("创建新节点 ++tot")
    CheckExist -- "否" --> Move("p = trie[p][id]")
    Create --> Move
    Move --> UpdatePass{"操作类型?"}
    UpdatePass -- "insert" --> IncPass("pass_cnt[p] 增加 1")
    UpdatePass -- "erase" --> DecPass("pass_cnt[p] 减少 1")
    IncPass --> Loop
    DecPass --> Loop
    Loop -- "遍历结束" --> UpdateEnd{"操作类型?"}
    UpdateEnd -- "insert" --> IncEnd("end_cnt[p] 增加 1")
    UpdateEnd -- "erase" --> DecEnd("end_cnt[p] 减少 1")
    IncEnd --> End("结束")
    DecEnd --> End

2. 计数查询 (Count)

graph TD
    Start("开始: 查询 s") --> Init("p = 0")
    Init --> Loop{"遍历字符 c"}
    Loop -- "还有字符" --> GetID("id = c 减去 'a'")
    GetID --> Check{"trie[p][id] 为 0?"}
    Check -- "是 (路径不存在)" --> RetZero("返回 0")
    Check -- "否" --> Move("p = trie[p][id]")
    Move --> Loop
    Loop -- "遍历结束" --> Type{"查询类型?"}
    Type -- "EqualTo" --> ResEnd("返回 end_cnt[p]")
    Type -- "StartingWith" --> ResPass("返回 pass_cnt[p]")

复杂度分析与易错点

1. 时间复杂度：
   • 所有操作均为 $O(L)$，$L$ 为字符串长度。
2. 空间复杂度：
   • $O(\sum L \times 26)$。需要注意 pass_cnt 和 end_cnt 数组的大小必须与 trie 数组的第一维一致。
3. 读题关键词：
   • “Exactly equal”：对应 end_cnt。
   • “Starting with”：对应 pass_cnt。
   • “Guarantee exists”：这个条件非常重要，它保证了你执行 erase 时不需要处理“减到负数”的情况，也简化了你是否需要删除物理节点的判断。
4. 注意点 (Mermaid 语法避错)：
   • 在实现逻辑中，trie[p][id] 指向的是子节点，更新 pass_cnt 时应更新子节点的计数，而不是当前父节点的计数，因为根节点 (p=0) 通常不计入长度为 1 的单词路径。

希望这个改写能帮助你理解 Trie 树的权值维护！当你能熟练处理 erase 操作时，你离掌握更复杂的可持久化字典树就不远了。准备好在草稿纸上模拟那两个计数器的变化了吗？