LeetCode 题解工作台
第 K 小的路径异或和
给定一棵以节点 0 为根的无向树，带有 n 个节点，按 0 到 n - 1 编号。每个节点 i 有一个整数值 vals[i] ，并且它的父节点通过 par[i] 给出。 从根节点 0 到节点 u 的 路径异或和 定义为从根节点到节点 u 的路径上所有节点 i 的 vals[i] 的按位异或，包括节点…
4
题型
1
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
class BinarySumTrie: def __init__(self):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一棵以节点 0 为根的无向树，带有 n 个节点，按 0 到 n - 1 编号。每个节点 i 有一个整数值 vals[i]，并且它的父节点通过 par[i] 给出。
从根节点 0 到节点 u 的 路径异或和 定义为从根节点到节点 u 的路径上所有节点 i 的 vals[i] 的按位异或，包括节点 u。
给定一个 2 维整数数组 queries，其中 queries[j] = [uj, kj]。对于每个查询，找到以 uj 为根的子树的所有节点中，第 kj 小 的 不同 路径异或和。如果子树中 不同 的异或路径和少于 kj，答案为 -1。
返回一个整数数组，其中第 j 个元素是第 j 个查询的答案。
在有根树中，节点 v 的子树包括 v 以及所有经过 v 到达根节点路径上的节点，即 v 及其后代节点。
示例 1：
输入：par = [-1,0,0], vals = [1,1,1], queries = [[0,1],[0,2],[0,3]]
输出：[0,1,-1]
解释：
路径异或值：
- 节点 0：
1 - 节点 1：
1 XOR 1 = 0 - 节点 2：
1 XOR 1 = 0
0 的子树：以节点 0 为根的子树包括节点 [0, 1, 2]，路径异或值为 [1, 0, 0]。不同的异或值为 [0, 1]。
查询：
queries[0] = [0, 1]：节点 0 的子树中第 1 小的不同路径异或值为 0。queries[1] = [0, 2]：节点 0 的子树中第 2 小的不同路径异或值为 1。queries[2] = [0, 3]：由于子树中只有两个不同路径异或值，答案为 -1。
输出：[0, 1, -1]
示例 2：
输入：par = [-1,0,1], vals = [5,2,7], queries = [[0,1],[1,2],[1,3],[2,1]]
输出：[0,7,-1,0]
解释：
路径异或值：
- 节点 0：
5 - 节点 1：
5 XOR 2 = 7 - 节点 2：
5 XOR 2 XOR 7 = 0
子树与不同路径异或值：
- 0 的子树：以节点 0 为根的子树包含节点
[0, 1, 2]，路径异或值为[5, 7, 0]。不同的异或值为[0, 5, 7]。 - 1 的子树：以节点 1 为根的子树包含节点
[1, 2]，路径异或值为[7, 0]。不同的异或值为[0, 7]。 - 2 的子树：以节点 2 为根的子树包含节点
[2]，路径异或值为[0]。不同的异或值为[0]。
查询：
queries[0] = [0, 1]：节点 0 的子树中，第 1 小的不同路径异或值为 0。queries[1] = [1, 2]：节点 1 的子树中，第 2 小的不同路径异或值为 7。queries[2] = [1, 3]：由于子树中只有两个不同路径异或值，答案为 -1。queries[3] = [2, 1]：节点 2 的子树中，第 1 小的不同路径异或值为 0。
输出：[0, 7, -1, 0]
提示：
1 <= n == vals.length <= 5 * 1040 <= vals[i] <= 105par.length == npar[0] == -1- 对于
[1, n - 1]中的i，0 <= par[i] < n 1 <= queries.length <= 5 * 104queries[j] == [uj, kj]0 <= uj < n1 <= kj <= n- 输出保证父数组
par表示一棵合法的树。
解题思路
方法一
class BinarySumTrie:
def __init__(self):
self.count = 0
self.children = [None, None]
def add(self, num: int, delta: int, bit=17):
self.count += delta
if bit < 0:
return
b = (num >> bit) & 1
if not self.children[b]:
self.children[b] = BinarySumTrie()
self.children[b].add(num, delta, bit - 1)
def collect(self, prefix=0, bit=17, output=None):
if output is None:
output = []
if self.count == 0:
return output
if bit < 0:
output.append(prefix)
return output
if self.children[0]:
self.children[0].collect(prefix, bit - 1, output)
if self.children[1]:
self.children[1].collect(prefix | (1 << bit), bit - 1, output)
return output
def exists(self, num: int, bit=17):
if self.count == 0:
return False
if bit < 0:
return True
b = (num >> bit) & 1
return self.children[b].exists(num, bit - 1) if self.children[b] else False
def find_kth(self, k: int, bit=17):
if k > self.count:
return -1
if bit < 0:
return 0
left_count = self.children[0].count if self.children[0] else 0
if k <= left_count:
return self.children[0].find_kth(k, bit - 1)
elif self.children[1]:
return (1 << bit) + self.children[1].find_kth(k - left_count, bit - 1)
else:
return -1
class Solution:
def kthSmallest(
self, par: List[int], vals: List[int], queries: List[List[int]]
) -> List[int]:
n = len(par)
tree = [[] for _ in range(n)]
for i in range(1, n):
tree[par[i]].append(i)
path_xor = vals[:]
narvetholi = path_xor
def compute_xor(node, acc):
path_xor[node] ^= acc
for child in tree[node]:
compute_xor(child, path_xor[node])
compute_xor(0, 0)
node_queries = defaultdict(list)
for idx, (u, k) in enumerate(queries):
node_queries[u].append((k, idx))
trie_pool = {}
result = [0] * len(queries)
def dfs(node):
trie_pool[node] = BinarySumTrie()
trie_pool[node].add(path_xor[node], 1)
for child in tree[node]:
dfs(child)
if trie_pool[node].count < trie_pool[child].count:
trie_pool[node], trie_pool[child] = (
trie_pool[child],
trie_pool[node],
)
for val in trie_pool[child].collect():
if not trie_pool[node].exists(val):
trie_pool[node].add(val, 1)
for k, idx in node_queries[node]:
if trie_pool[node].count < k:
result[idx] = -1
else:
result[idx] = trie_pool[node].find_kth(k)
dfs(0)
return result
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the DFS traversal for computing XOR sums, which takes O(n). Query resolution is efficient using ordered sets, and each query can be handled in O(log n) for set operations, leading to an overall time complexity of O(n + q log n), where n is the number of nodes and q is the number of queries. Space complexity is O(n) for storing XOR values and sets. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate can apply DFS traversal in a tree structure to compute path XORs.
- question_mark
Evaluate their ability to handle large inputs and optimize query resolution using data structures like ordered sets.
- question_mark
Assess how well they manage state tracking during traversal to efficiently answer multiple queries.
常见陷阱
外企场景- error
Not optimizing the query resolution by failing to use efficient data structures like ordered sets.
- error
Incorrectly handling XOR sums when there are fewer than k distinct values in the subtree.
- error
Missing edge cases where no valid XOR sum exists for a query, leading to incorrect results.
进阶变体
外企场景- arrow_right_alt
Consider variants where the tree structure is balanced or skewed, which could affect traversal efficiency.
- arrow_right_alt
Try variations where the query asks for the maximum XOR sum instead of the kth smallest.
- arrow_right_alt
Explore optimizations for larger trees with a high number of queries.