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
| class Solution:
def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:
class xorTrie:
def __init__(self):
self.n = [None, None]
def insert(self, val, h=1 << 44):
if h:
b = bool(val & h)
if self.n[b] is None:
self.n[b] = xorTrie()
self.n[b].insert(val - (h if b else 0), h >> 1)
def maxXor(self, val, h=1 << 44):
if h == 0 or self.n[0] == self.n[1]:
return 0
b = bool(val & h)
if self.n[not b] is not None:
return h + self.n[not b].maxXor(val - (h if b else 0), h >> 1)
return self.n[b].maxXor(val - (h if b else 0), h >> 1)
def treeSum(i, p, al, sums):
for j in al[i]:
if j != p:
sums[i] += treeSum(j, i, al, sums)
return sums[i]
def dfs(i, p, al, sums, t):
res = t.maxXor(sums[i])
for j in al[i]:
if j != p:
res = max(res, dfs(j, i, al, sums, t))
t.insert(sums[i])
return res
al = [[] for _ in range(n)]
for e in edges:
al[e[0]].append(e[1])
al[e[1]].append(e[0])
sums = [int(v) for v in values]
treeSum(0, -1, al, sums)
return dfs(0, -1, al, sums, xorTrie())
|