企业官网建设流程全解析

Python3 实现（二进制 Trie + 启发式合并）

这是 LeetCode 3590 的标准正解，使用二进制 Trie维护子树内所有路径异或和，并通过启发式合并（Small-to-Large）控制复杂度。

解题思路（简要）

1. 预处理路径异或和

   • xor[u] = xor[par[u]] ^ vals[u]

2. 二进制 Trie

   • 存储子树内所有xor值（自动去重）

   • 每个节点维护：

     • cnt：子树中不同数值的个数

     • end：当前节点是否为某个数值的结尾

   • 支持：

     • insert

     • query_kth（第 k 小）

3. 启发式合并

   • 后序 DFS

   • 将较小的 Trie 合并到较大的 Trie

   • 每个数值最多被插入O(log n)次

4. 复杂度

   • 时间：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 版本

如果你愿意，我可以再给你一个：

• ✅更简洁但稍慢的SortedList版本

• ✅逐行讲解版（适合面试口述）

• ✅Flink 相关算法题衔接版

直接说你想要哪一个 👍