# 离线算法 + 字典树
class Trie:
left: "Trie" = None
right: "Trie" = None
# 由于我们的字典树需要支持删除数的操作
# 因此这里使用 cnt 变量进行记录该节点对应的数的个数
cnt: int = 0
class Solution:
# 最大的数的二进制表示不会超过 18 位
# 那么二进制位的下标范围为 [0, 17]
MAXD = 17
def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:
n = len(parents)
# 将 parents 存储为树的形式，方便进行深度优先遍历
edges = defaultdict(list)
# 找出根节点
root = -1
for i, parent in enumerate(parents):
if parent == -1:
root = i
else:
edges[parent].append(i)
q = len(queries)
# 使用离线的思想，stored[i] 存储了所有节点 i 对应的询问
stored = defaultdict(list)
ans = [0] * q
for i, (node, val) in enumerate(queries):
stored[node].append((i, val))
r = Trie()
# 向字典树添加一个数
def trie_insert(x: int) -> None:
cur = r
for i in range(Solution.MAXD, -1, -1):
if x & (1 << i):
if not cur.right:
cur.right = Trie()
cur = cur.right
else:
if not cur.left:
cur.left = Trie()
cur = cur.left
cur.cnt += 1
# 对于给定的 x，返回字典树中包含的数与 x 进行异或运算可以达到的最大值
def trie_query(x: int) -> int:
cur, ret = r, 0
for i in range(Solution.MAXD, -1, -1):
if x & (1 << i):
if cur.left and cur.left.cnt:
ret |= (1 << i)
cur = cur.left
else:
cur = cur.right
else:
if cur.right and cur.right.cnt:
ret |= (1 << i)
cur = cur.right
else:
cur = cur.left
return ret
# 从字典树中删除一个数
def trie_erase(x: int) -> None:
cur = r
for i in range(Solution.MAXD, -1, -1):
if x & (1 << i):
cur = cur.right
else:
cur = cur.left
cur.cnt -= 1
# 深度优先遍历
def dfs(u: int) -> None:
trie_insert(u)
for idx, num in stored[u]:
ans[idx] = trie_query(num)
for v in edges[u]:
dfs(v)
trie_erase(u)
dfs(root)
return ans
/**
* 首先离线询问，将询问按照 nodei 分组。
* 然后根据 parents 建树，从根开始 DFS，每访问一个节点 v，就将其插入字典树，
* 然后回答当前节点 v 对应的所有询问，最后在递归结束时将 v 从字典树中删去。
*/
type node struct {
son [2]*node
cnt int
}
type trie struct{ root *node }
func (t *trie) put(v int) *node {
o := t.root
for i := 17; i >= 0; i-- {
b := v >> i & 1
if o.son[b] == nil {
o.son[b] = &node{}
}
o = o.son[b]
o.cnt++
}
return o
}
func (t *trie) del(v int) *node {
o := t.root
for i := 17; i >= 0; i-- {
o = o.son[v>>i&1]
o.cnt-- // 删除操作只需要减少 cnt 就行，cnt 为 0 就视作删掉了该节点
}
return o
}
func (t *trie) maxXor(v int) (ans int) {
o := t.root
for i := 17; i >= 0; i-- {
b := v >> i & 1
if o.son[b^1] != nil && o.son[b^1].cnt > 0 {
ans |= 1 << i
b ^= 1
}
o = o.son[b]
}
return
}
func maxGeneticDifference(parents []int, queries [][]int) []int {
n := len(parents)
// 建树
g := make([][]int, n)
var root int
for v, pa := range parents {
if pa == -1 {
root = v
} else {
g[pa] = append(g[pa], v)
}
}
// 离线，将查询分组
type query struct{ val, i int }
qs := make([][]query, n)
for i, q := range queries {
qs[q[0]] = append(qs[q[0]], query{q[1], i})
}
ans := make([]int, len(queries))
t := &trie{&node{}}
// 遍历整棵树，每访问一个节点就将其插入 trie 树，访问结束时将其从 trie 中删去
var dfs func(int)
dfs = func(v int) {
t.put(v)
for _, q := range qs[v] {
ans[q.i] = t.maxXor(q.val)
}
for _, w := range g[v] {
dfs(w)
}
t.del(v)
}
dfs(root)
return ans
}
