题目大意

维护一棵初始只有根节点 $1$ 的树，支持两种操作：

• $\texttt{Add x y}$：给节点 $x$ 添加一个儿子，边权为 $y$，新节点编号为当前节点数 $+1$
• $\texttt{Query a b}$：查询从节点 $a$ 到节点 $b$ 的子树中任意节点的路径异或值的最大值

路径长度定义为路径上所有边权的异或值。

问题分析

关键性质

1. 异或路径性质： 设 $dist[u]$ 表示从根节点 $1$ 到节点 $u$ 的路径异或值，那么：

   $$dist(u,v) = dist[u] \oplus dist[v]$$

   其中 $dist(u,v)$ 表示节点 $u$ 到 $v$ 的路径异或值。

2. 问题转化： 对于查询 $\texttt{Query a b}$，我们需要在 $b$ 的子树中找到节点 $v$，使得：

   $$dist(a,v) = dist[a] \oplus dist[v]$$

   的值最大。

   由于 $dist[a]$ 是固定的，问题转化为在 $b$ 的子树中寻找与 $dist[a]$ 异或值最大的 $dist[v]$。

数据结构需求

• 支持子树查询：需要在指定节点的子树范围内进行查询
• 支持动态插入：树是动态构建的
• 高效异或最大值查询：需要快速找到与给定值异或最大的元素

算法设计

方法一：可持久化字典树 + DFS序

核心思路：

1. 对树进行DFS遍历，得到每个节点的DFS序
2. 按照DFS序建立可持久化字典树
3. 对于每个查询，在 $b$ 的子树对应的DFS序区间内查询与 $dist[a]$ 异或的最大值

具体步骤：

1. 预处理：

   • 进行DFS，记录每个节点的入序 $in[u]$ 和出序 $out[u]$
   • 计算每个节点到根的路径异或值 $dist[u]$

2. 构建数据结构：

   • 按照DFS序依次将 $dist$ 值插入可持久化字典树
   • 得到版本序列 $root[1], root[2], \dots, root[n]$

3. 查询处理：

   • 对于查询 $\texttt{Query a b}$，确定 $b$ 的子树在DFS序中的区间 $[in[b], out[b]]$
   • 在可持久化字典树的版本 $root[out[b]]$ 和 $root[in[b]-1]$ 之间查询与 $dist[a]$ 异或的最大值

复杂度分析：

• 时间复杂度：$O(Q \log \max(y))$，其中 $\max(y) \leq 2^{30}$
• 空间复杂度：$O(Q \log \max(y))$

方法二：启发式合并 + 字典树

核心思路：

1. 为每个节点维护一个字典树，存储其子树中所有节点的 $dist$ 值
2. 添加节点时，自底向上合并子树信息
3. 查询时直接在 $b$ 的字典树中查询

具体步骤：

1. 插入操作：

   • 新节点 $u$ 的 $dist[u] = dist[parent] \oplus edgeWeight$
   • 将 $dist[u]$ 插入 $u$ 的字典树

2. 合并策略：

   • 使用启发式合并（小的合并到大的）
   • 维护每个节点的字典树大小

3. 查询处理：

   • 对于 $\texttt{Query a b}$，在 $b$ 的字典树中查询与 $dist[a]$ 异或的最大值

复杂度分析：

• 时间复杂度：$O(Q \log^2 \max(y))$（由于启发式合并）
• 空间复杂度：$O(Q \log \max(y))$

实现细节

字典树设计

由于 $y \leq 2^{30}$，字典树深度为 $31$：

struct TrieNode {
    int child[2];
    int cnt;  // 子树大小（用于可持久化）
};

可持久化字典树操作

• insert(old_root, value)：插入新值，返回新根
• query(l_root, r_root, value)：在区间 $[l, r]$ 中查询与 $value$ 异或的最大值

树结构维护

• 使用邻接表存储树结构
• 维护父节点信息、深度信息
• 动态更新DFS序

特殊情况处理

1. 空子树：确保查询时区间有效
2. 根节点查询：$b = 1$ 时查询整个树
3. 自查询：$a = b$ 时包含节点自身

优化技巧

1. 二进制位处理：从高位到低位处理，贪心选择异或值大的分支
2. 内存管理：可持久化数据结构注意内存分配
3. 输入输出优化：由于 $Q$ 较大，建议使用快速IO

总结

本题是一道结合了树结构、异或操作和可持久化数据结构的经典问题。核心在于将路径异或查询转化为前缀异或的异或最大值查询，并利用DFS序将子树查询转化为区间查询。可持久化字典树提供了优雅的解决方案，能够在 $O(\log \max(y))$ 时间内完成每个查询。

关键洞察：利用异或运算的性质和树的DFS序，将复杂的树路径查询转化为经典的可持久化异或最大值问题。