根树节点62位二进制最长公共前缀查询的高效解法问询

你提到的暴力遍历路径的思路在树为链式结构时会退化到O(NQ)的时间复杂度，无法适配1e5规模的输入，这里提供两种时间复杂度为O(62*(N+Q))的可行方案，均能轻松满足约束要求。

方案一：离线DFS + 普通二进制Trie（实现更简单） #

核心思路是通过深度优先遍历的进入/回溯时机，动态维护根节点到当前节点的所有权值构成的二进制Trie，到达节点时直接回答挂载在该节点的所有查询：

• 第一步：用邻接表建树，提前标记每个节点的父节点，避免DFS时走回父节点。
• 第二步：离线处理所有查询，将每个(V, X)查询挂载到节点X的查询列表中，同时记录查询的原始下标，方便后续按输入顺序输出答案。
• 第三步：构建支持计数的二进制Trie，每个Trie节点存储两个子节点指针（对应二进制位0/1）和count字段，统计当前路径覆盖的数字数量。
• 第四步：从根节点1开始DFS遍历：
  1. 进入当前节点u时，将A[u]的62位二进制从最高位到最低位依次插入Trie，每经过一个Trie节点就将其count加1。
  2. 处理所有挂载在u上的查询：对查询值V，同样从最高位到最低位遍历其二进制位，每一步优先尝试走Trie中与当前位相同的子节点（仅当子节点存在且count>0时可走），累计能走的步数就是本次查询的最长公共前缀长度，存入答案数组对应位置。
  3. 递归遍历u的所有子节点。
  4. 回溯离开u时，将A[u]从Trie中删除：按插入路径再次遍历，每经过一个Trie节点就将其count减1。

方案二：在线可持久化二进制Trie（支持动态查询） #

如果要求在线处理查询（无法提前拿到所有查询列表），可以用可持久化Trie实现：

• 第一步：同样先建树，按DFS/BFS顺序遍历节点。
• 第二步：每个节点u对应一个独立的Trie版本，版本u基于父节点的Trie版本插入A[u]生成。可持久化插入时不会修改原有版本的节点，只会新增插入路径上的节点，总空间复杂度为O(62*N)，适配1e5的规模要求。
• 第三步：处理查询(V, X)时，直接使用节点X对应的Trie版本，和方案一的查询逻辑一致，从最高位开始优先走与V当前位相同的分支，累计可走步数即为答案。

两种方案的核心都是利用Trie的前缀匹配特性，规避了逐一枚举路径节点的开销，时间复杂度均能达到要求，离线方案实现难度更低，更推荐优先使用。

内容的提问来源于stack exchange，提问作者tusharRawat