Python3 实现二进制 Trie 启发式合并这是 LeetCode 3590 的标准正解使用二进制 Trie维护子树内所有路径异或和并通过启发式合并Small-to-Large控制复杂度。解题思路简要预处理路径异或和xor[u] xor[par[u]] ^ vals[u]二进制 Trie存储子树内所有xor值自动去重每个节点维护cnt子树中不同数值的个数end当前节点是否为某个数值的结尾支持insertquery_kth第 k 小启发式合并后序 DFS将较小的 Trie 合并到较大的 Trie每个数值最多被插入O(log n)次复杂度时间O((n log n q) · log C)空间O(n log C)Python3 代码from collections import defaultdict from typing import List class TrieNode: __slots__ (children, cnt, end) def __init__(self): self.children [None, None] # 0, 1 self.cnt 0 # 子树中不同数值个数 self.end False # 是否为一个数值的结尾 class Solution: def kthSmallest(self, par: List[int], vals: List[int], queries: List[List[int]]) - List[int]: n, q len(vals), len(queries) g defaultdict(list) for i in range(1, n): g[par[i]].append(i) # 按节点分组查询 qs [[] for _ in range(n)] for i, (u, k) in enumerate(queries): qs[u].append((k, i)) ans [-1] * q MAX_BIT 17 # 2^17 1e5 # ---------- Trie 操作 ---------- def insert(node: TrieNode, x: int) - bool: cur node path [cur] i MAX_BIT while i 0: b (x i) 1 if not cur.children[b]: break cur cur.children[b] path.append(cur) i - 1 if i 0 and cur.end: return False # 已存在 while i 0: b (x i) 1 nxt TrieNode() cur.children[b] nxt cur nxt path.append(cur) i - 1 cur.end True for nd in path: nd.cnt 1 return True def collect(node: TrieNode, prefix: int, vals: list): if not node: return if node.end: vals.append(prefix) collect(node.children[0], prefix 1, vals) collect(node.children[1], (prefix 1) | 1, vals) def merge(dst: TrieNode, src: TrieNode): tmp [] collect(src, 0, tmp) for v in tmp: insert(dst, v) def query_kth(node: TrieNode, k: int) - int: if not node or k 0 or k node.cnt: return -1 cur node res 0 for i in range(MAX_BIT, -1, -1): left cur.children[0] left_cnt left.cnt if left else 0 if k left_cnt: cur left res 1 else: k - left_cnt cur cur.children[1] res (res 1) | 1 return res # ---------- DFS 启发式合并 ---------- def dfs(u: int, cur_xor: int) - TrieNode: cur_xor ^ vals[u] # 找最大子 Trie big None max_size -1 for v in g[u]: child_trie dfs(v, cur_xor) if child_trie and child_trie.cnt max_size: max_size child_trie.cnt big child_trie if big is None: big TrieNode() # 合并其他子 Trie for v in g[u]: t tries[v] if t is big: continue merge(big, t) # 插入当前节点 insert(big, cur_xor) tries[u] big # 回答查询 for k, idx in qs[u]: ans[idx] query_kth(big, k) return big tries [None] * n dfs(0, 0) return ans示例sol Solution() par [-1, 0, 0, 1, 1, 2, 2] vals [1, 2, 3, 4, 5, 6, 7] queries [[0, 1], [1, 2], [2, 3]] print(sol.kthSmallest(par, vals, queries)) # 输出: [0, 6, 5]关键点总结✅二进制 Trie天然适合处理“第 k 小异或值”✅启发式合并避免暴力合并保证n log n✅去重通过end标记保证只统计一次✅Python 优化__slots__减少内存占用对比 Java 版本方面JavaPythonTrie 实现数组 显式对象字典 __slots__合并方式直接遍历 TreeMap先收集再插入性能更快稍慢但仍可 AC如果你愿意我可以再给你一个✅更简洁但稍慢的SortedList版本✅逐行讲解版适合面试口述✅Flink 相关算法题衔接版直接说你想要哪一个