题解：家族姓氏匹配问题

核心思想

本题的关键在于利用哈希技术快速判断 Bajtazar 的姓氏是否能由底层祖先姓氏通过任意顺序拼接生成。

重要公式与算法

1. 问题转化

对于完全二叉树的每个节点，其可能生成的姓氏集合由左右子树可能生成集合的有序拼接决定：

$$T(v) = \{L \oplus R,\ R \oplus L\}$$

其中 $\oplus$ 表示字符串连接。

2. 哈希表示法

对每个节点维护其规范化的哈希值：

$$H(v) = \min\left(H(left) \times B^{len/2} + H(right),\ H(right) \times B^{len/2} + H(left)\right) $$

其中：

• $B$ 是哈希基数（$1313131$）
• $P$ 是模数（$2^{61} - 1$）
• $len$ 是当前节点字符串长度

3. 规范化处理

关键技巧：在每个节点处，总是取两个可能拼接顺序中字典序较小的哈希值作为代表。这样：

• 如果两个子树能生成相同的字符串集合，它们的规范化哈希值必然相同
• 通过比较根节点的规范化哈希值，即可判断 Bajtazar 姓氏是否可达

4. 动态更新

当修改单个字符时：

• 只需更新从对应叶子到根的路径上的所有节点哈希值
• 每次更新时间复杂度：$O(n)$
• 总体复杂度：$O(n(q + 2^n))$

算法优势

这种方法避免了显式存储所有可能的字符串，通过哈希值的规范化比较，高效解决了大规模动态判断问题，能够在 $n \leq 20$、$q \leq 10^6$ 的数据范围内快速响应查询。