难度: Hard
Submission
运行时间: 1117 ms
内存: 130.9 MB
class Trie(object):
def __init__(self):
self.l=None
self.r=None
self.lc=0
self.rc=0
def search(self,prefix):
node=self
res=0
for i,s in enumerate(prefix):
if node is None:
return 0
elif s=="1":
if node.l and node.lc>0:
res|=(1<<(44-i))
node=node.l
else:
node=node.r
else:
if node.r and node.rc>0:
res|=(1<<(44-i))
node=node.r
else:
node=node.l
return res
def insert(self,word):
node=self
for s in word:
if s=="0":
if not node.l:
node.l=Trie()
node.lc+=1
node=node.l
else:
if not node.r:
node.r=Trie()
node.rc+=1
node=node.r
def delete(self,word):
node=self
for s in word:
if s=="0":
node.lc-=1
node=node.l
else:
node.rc-=1
node=node.r
class Solution:
def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:
def tran(num):
s=bin(num)[2:]
n=len(s)
s="0"*(45-n)+s
return s
graph=defaultdict(list)
for u,v in edges:
graph[u].append(v)
graph[v].append(u)
graph[0].append(-1)
tree,ans=Trie(),0
vis=[0]*n
def getsum(x,fa):
vis[x]=values[x]
for y in graph[x]:
if y==fa: continue
vis[x]+=getsum(y,x)
return vis[x]
getsum(0,-1)
print(vis)
def dfs(x,fa):
nonlocal ans
total=vis[x]
s=tran(total)
cur=tree.search(s)
ans=max(ans,cur)
for y in graph[x]:
if y==fa: continue
dfs(y,x)
tree.insert(s)
dfs(0,-1)
return ans
Explain
这个题解采用了字典树(Trie)来处理最大异或值问题，其基本思路涉及建立一棵树，对树的每个子节点的值计算总和，并对总和进行字典树存储和查询以寻找可能的最大异或值。算法的主要步骤包括：1) 使用DFS遍历树，并计算每个节点作为根的子树中所有节点的值的总和；2) 使用二进制表示的总和构建字典树，以支持高效的最大异或值查找；3) 再次DFS遍历树，在每个节点处使用字典树查找当前节点的子树总和与已有的总和异或后的最大值。
时间复杂度: O(n*L)
空间复杂度: O(n*L)
class Trie(object):
def __init__(self):
self.l = None # 左子节点
self.r = None # 右子节点
self.lc = 0 # 左子节点计数
self.rc = 0 # 右子节点计数
def search(self, prefix):
node = self
res = 0
for i, s in enumerate(prefix):
if node is None:
return 0
elif s == '1':
if node.l and node.lc > 0:
res |= (1 << (44-i))
node = node.l
else:
node = node.r
else:
if node.r and node.rc > 0:
res |= (1 << (44-i))
node = node.r
else:
node = node.l
return res
def insert(self, word):
node = self
for s in word:
if s == '0':
if not node.l:
node.l = Trie()
node.lc += 1
node = node.l
else:
if not node.r:
node.r = Trie()
node.rc += 1
node = node.r
def delete(self, word):
node = self
for s in word:
if s == '0':
node.lc -= 1
node = node.l
else:
node.rc -= 1
node = node.r
class Solution:
def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:
def tran(num): # 转换数字为固定长度的二进制字符串
s = bin(num)[2:]
n = len(s)
s = '0'*(45-n) + s
return s
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
graph[0].append(-1)
tree, ans = Trie(), 0
vis = [0] * n
def getsum(x, fa): # DFS求子树和
vis[x] = values[x]
for y in graph[x]:
if y == fa: continue
vis[x] += getsum(y, x)
return vis[x]
getsum(0, -1)
print(vis)
def dfs(x, fa): # DFS查找最大异或值
nonlocal ans
total = vis[x]
s = tran(total)
cur = tree.search(s)
ans = max(ans, cur)
for y in graph[x]:
if y == fa: continue
dfs(y, x)
tree.insert(s)
dfs(0, -1)
return ans
Explore
在构建字典树时，我通过将每个节点的子树总和转化为45位的二进制字符串，并将这些字符串插入字典树中来确保字典树反映所有可能的异或组合。每一位二进制数代表的是该位为0还是1，字典树的每一层对应二进制字符串的一位，从而确保字典树可以覆盖所有可能的二进制组合。这种方法可以详尽地记录每一种可能的总和情况，使得在后续的查询中可以高效地找到与任意子树总和进行异或操作后可能得到的最大值。
选择字典树的原因在于其能够提供高效的最大异或值搜索功能。字典树可以根据二进制位的每一位进行分层存储和查找，使得在每一步都尽可能选择与当前位异或后结果最大的路径，即0与1异或结果为1，1与0异或结果为1。这种结构比哈希表和平衡树在查找最大异或值时更加直接和高效，因为字典树直接利用二进制位的特性进行分支，而不需要像哈希表或平衡树那样处理更多的碰撞和平衡问题。
在字典树的`search`方法中，当当前位为1且左子节点存在时优先选择左子节点，是因为我们希望找到与当前位异或结果最大的值。字典树的左子节点代表0，右子节点代表1。当当前位为1时，与0异或（即走向左子节点）的结果是1，这比与1异或（即走向右子节点）的结果0更大。这样的选择可以确保每一步都尽可能地增大异或的结果，从而找到可能的最大异或值。
确实，在极端情况下，每个节点都需要进行插入和搜索操作可能会影响字典树的性能，特别是当树结构高度不平衡时。这种情况下，字典树的深度可能变得很大，从而导致操作的时间复杂度增加。一种可能的优化策略是限制字典树的深度或使用迭代深化搜索，从而在保持效率的同时减少深度。另一种策略是使用更加平衡的数据结构来辅助字典树，例如平衡二叉搜索树，以此来平衡字典树的深度和搜索效率。