算法解析 本题的核心在于将树上问题转化为区间问题，并利用可持久化 01-Trie 维护前缀信息以支持异或最大值查询。 1. 前置知识：01-Trie 与可持久化 01-Trie：将数字按二进制位（从高位到低位）插入字典树。查询与 x 异或的最大值时，贪心地选择与 x 当前位相反的分支。 可持久化：每次插入新节点时，复制路径上的节点，从而保留历史版本。这样，版本 r 与版本 l−1 的 Trie 相减，即可得到区间 [l,r] 内所有数的集合。 2. 操作 1：子树查询 子树查询是经典的 DFS 序 + 可持久化 Trie 问题。 转化：通过一次 DFS，求出每个节点的入栈时间戳 dfn[u] 和出栈时间戳 out[u]。那么节点 x 的子树恰好对应区间 [dfn[x],out[x]]。 构建：按照 DFS 序依次将节点权值插入可持久化 Trie。记 root_dfn[i] 为插入第 i 个节点后的 Trie 根节点。 查询：查询区间 [dfn[x],out[x]] 时，利用 root_dfn[out[x]] 和 root_dfn[dfn[x]−1] 进行差分，在得到的 Trie 上贪心求与 y 的异或最大值。 3. 操作 2：路径查询 路径查询需要利用 LCA 和 树上差分 的思想。 构建：我们需要另一套可持久化 Trie，按照“根到节点”的路径构建。记 root_path[u] 为从根节点 1 到节点 u 的路径上所有节点权值构成的 Trie。 转化：对于路径 x→y，设其 LCA 为 l，父亲为 f。路径上的权值集合可以表示为： {1→x}∪{1→y}−{1→l}−{1→f} 查询：在四个版本 root_path[x],root_path[y],root_path[l],root_path[f] 的 Trie 上同时进行差分，统计每一位上 0 和 1 的数量，然后贪心选择与 z 当前位相反的方向。 4. 关键细节 两套 Trie：必须建立两套独立的可持久化 Trie，一套用于子树（基于 DFS 序），一套用于路径（基于根到节点）。 LCA 处理：使用倍增法预处理，以便 O(logn) 查询 LCA 及其父节点。 空间复杂度：每个插入操作最多新增 O(logV) 个节点（V 为值域），总空间约为 O((n+Q)logV)，需开足够大的数组（通常 n×32×2 以上）。 复杂度分析 时间复杂度：O((n+Q)logV)，其中 V=2的30次方。 空间复杂度：O(nlogV)。