根据搜索结果这是 LeetCode 3590 第 K 小的路径异或和 的 Go 实现。题目理解- 给定一棵以 0 为根的树每个节点有值 vals[i]- 路径异或和从根节点 0 到节点 u 的路径上所有节点值的异或- 每个查询 [uj, kj]在以 uj 为根的子树中找第 kj 小的不同路径异或和不足 kj 个则返回 -1核心思路1. 预处理DFS 计算每个节点从根到该节点的路径异或和 pathXor[u]2. 子树查询需要快速获取子树中不同的 pathXor 值并找第 k 小3. 树上启发式合并DSU on Tree / Small-to-Large后序遍历将小子树的集合合并到大子树保证每个元素最多被移动 O(log n) 次4. 数据结构用二进制 Trie 维护不同值的集合支持 add、exists、find_kth 操作Go 实现gopackage main// 二进制 Trie 节点type TrieNode struct {count int // 该子树中元素个数children [2]*TrieNode // 0 和 1 两个子节点}func NewTrieNode() *TrieNode {return TrieNode{count: 0,children: [2]*TrieNode{nil, nil},}}// 向 Trie 中添加/删除一个数 (delta 1 添加, -1 删除)func (t *TrieNode) Add(num int, delta int, bit int) {t.count deltaif bit 0 {return}b : (num bit) 1if t.children[b] nil {t.children[b] NewTrieNode()}t.children[b].Add(num, delta, bit-1)}// 收集 Trie 中所有数func (t *TrieNode) Collect(prefix int, bit int, output *[]int) {if t.count 0 {return}if bit 0 {*output append(*output, prefix)return}if t.children[0] ! nil {t.children[0].Collect(prefix, bit-1, output)}if t.children[1] ! nil {t.children[1].Collect(prefix|(1bit), bit-1, output)}}// 判断一个数是否在 Trie 中func (t *TrieNode) Exists(num int, bit int) bool {if t.count 0 {return false}if bit 0 {return true}b : (num bit) 1if t.children[b] nil {return false}return t.children[b].Exists(num, bit-1)}// 找第 k 小的数 (1-indexed)func (t *TrieNode) FindKth(k int, bit int) int {if k t.count {return -1}if bit 0 {return 0}leftCount : 0if t.children[0] ! nil {leftCount t.children[0].count}if k leftCount {return t.children[0].FindKth(k, bit-1)}if t.children[1] ! nil {return (1 bit) t.children[1].FindKth(k-leftCount, bit-1)}return -1}func kthSmallest(par []int, vals []int, queries [][]int) []int {n : len(par)// 建树tree : make([][]int, n)for i : 1; i n; i {tree[par[i]] append(tree[par[i]], i)}// 计算从根到每个节点的路径异或和pathXor : make([]int, n)copy(pathXor, vals)var computeXor func(node, acc int)computeXor func(node, acc int) {pathXor[node] ^ accfor _, child : range tree[node] {computeXor(child, pathXor[node])}}computeXor(0, 0)// 按节点分组查询nodeQueries : make(map[int][][2]int) // node - [(k, idx)]for idx, q : range queries {u, k : q[0], q[1]nodeQueries[u] append(nodeQueries[u], [2]int{k, idx})}// 结果res : make([]int, len(queries))// Trie 池每个节点一个triePool : make([]*TrieNode, n)// DFS 小到大合并var dfs func(node int)dfs func(node int) {// 初始化当前节点的 TrietriePool[node] NewTrieNode()triePool[node].Add(pathXor[node], 1, 17)for _, child : range tree[node] {dfs(child)// 小到大合并确保 triePool[node] 是较大的那个if triePool[node].count triePool[child].count {triePool[node], triePool[child] triePool[child], triePool[node]}// 将子树的所有不同值合并到当前节点var vals []inttriePool[child].Collect(0, 17, vals)for _, v : range vals {if !triePool[node].Exists(v, 17) {triePool[node].Add(v, 1, 17)}}}// 回答当前节点的所有查询for _, q : range nodeQueries[node] {k, idx : q[0], q[1]if triePool[node].count k {res[idx] -1} else {res[idx] triePool[node].FindKth(k, 17)}}}dfs(0)return res}复杂度分析指标 复杂度 说明时间 O(n log n · B q · B) B18 为二进制位数小到大合并保证每个元素最多移动 O(log n) 次空间 O(n · B) Trie 节点总数关键点1. 二进制 Trie用 18 位0 vals[i] 1e5异或结果也在这个范围附近维护不同值支持 O(B) 的 add、exists、find_kth2. 小到大合并每次将小子树的 Trie 合并到大子树保证总复杂度为 O(n log n)3. 去重合并时先 Exists 检查避免重复插入相同的 pathXor 值