1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class TrieNode:
def __init__(self):
self.child = {}
self.go = 0 # Number of elements goes through this node
def increase(self, number, d):
current = self
for i in range(17, -1, -1):
bit = (number >> i) & 1
if bit not in current.child:
current.child[bit] = TrieNode()
current = current.child[bit]
current.go += d
def findMax(self, number):
current, answer = self, 0
for i in range(17, -1, -1):
bit = (number >> i) & 1
if (1-bit) in current.child and current.child[1-bit].go > 0:
current = current.child[1 - bit]
answer |= (1 << i)
else:
current = current.child[bit]
return answer
class Solution:
def maxGeneticDifference(self, parents: List[int], qs: List[List[int]]) -> List[int]:
n, m, root = len(parents), len(qs), -1
answer, trieNode = [-1] * m, TrieNode()
graph, queryByNode = [[] for _ in range(n)], [[] for _ in range(n)]
for i, p in enumerate(parents):
if p == -1:
root = i
else:
graph[p].append(i)
for i, q in enumerate(qs):
queryByNode[q[0]].append((q[1], i)) # node -> list of pairs (val, idx)
def dfs(u):
trieNode.increase(u, 1)
for val, idx in queryByNode[u]:
answer[idx] = trieNode.findMax(val)
for v in graph[u]:
dfs(v)
trieNode.increase(u, -1)
dfs(root)
return answer
|