难度: Medium
Submission
运行时间: 531 ms
内存: 96.7 MB
class Solution(object):
def maxScore(self, edges):
tree = {}
for index, [father, weight] in enumerate(edges):
child_dict = tree.get(father, {})
child_dict[index] = weight
tree[father] = child_dict
def dfs(root) -> list: #[with_root, without_root]
nonlocal tree
if root not in tree:
return [0, 0]
child_value = {}
for child in tree[root].keys():
child_value[child] = dfs(child)
child_value_max = {}
for child in child_value.keys():
child_value_max[child] = max(child_value[child])
without_root = sum(child_value_max.values())
with_root = 0
for child in tree[root].keys():
with_root = max([with_root, without_root - child_value_max[child] + child_value[child][1] + tree[root][child]])
return with_root, without_root
return max(dfs(0))
Explain
该题解采用深度优先搜索(DFS)来解决问题。首先，它构造了一个树的表示，其中使用字典来存储每个节点的子节点及其对应的边权重。然后定义了一个递归函数 `dfs`，该函数对于每个节点返回两个值：包含当前节点的最大得分和不包含当前节点的最大得分。对于每个子节点，分别计算包含和不包含该子节点时的最大得分，并聚合这些得分来计算当前节点的最大得分。最后，从根节点调用 `dfs` 函数，并返回包含或不包含根节点的最大值。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution(object):
def maxScore(self, edges):
tree = {}
for index, [father, weight] in enumerate(edges):
child_dict = tree.get(father, {})
child_dict[index] = weight
tree[father] = child_dict
def dfs(root) -> list: #[with_root, without_root]
nonlocal tree
if root not in tree:
return [0, 0]
child_value = {}
for child in tree[root].keys():
child_value[child] = dfs(child)
child_value_max = {}
for child in child_value.keys():
child_value_max[child] = max(child_value[child])
without_root = sum(child_value_max.values())
with_root = 0
for child in tree[root].keys():
with_root = max([with_root, without_root - child_value_max[child] + child_value[child][1] + tree[root][child]])
return with_root, without_root
return max(dfs(0))
Explore
在定义DFS函数时，返回的两个值`[with_root, without_root]`分别代表两种情况下的最大得分。`with_root`指包括当前节点在内时的最大得分，而`without_root`则指不包括当前节点时其他子树能达到的最大得分。这种设计允许在递归过程中灵活选择是否包括某个节点来优化得分，尤其是在存在权重的情况下。
在构建树结构时，题解中通过遍历给定的边列表来构建父节点到子节点的映射。为了确保没有遗漏任何节点，特别是只作为子节点出现的节点，在构建过程中还需要考虑这些子节点可能没有在字典的键中出现。可以通过在遍历边的同时，将子节点也记录下来，并在构建完成后检查哪些节点未被作为键记录，这些节点则是只作为子节点出现的节点。在实际编码中，我们还需要确保每个节点都能在遍历过程中被访问到，可能需要额外的数据结构来标记节点的访问状态。
这种计算方式考虑了包括当前节点在内时，对于每个子节点可以选择不包括该子节点本身（使用其子节点的最大得分）而加上与当前节点连接的边的权重来优化得分。`without_root - child_value_max[child]`表示从不包含当前节点的总得分中移除该子节点的最大得分，`+ child_value[child][1]`再加上不包括该子节点但包含其子树的得分，`+ tree[root][child]`最后加上当前节点与该子节点的连接边权重。这种方式能够确保在决定包括某个节点时，能够获得最优的得分组合。
在处理大规模数据时，使用字典来存储节点和边的关系通常是有效的，因为字典提供了平均常数时间复杂度的查找、插入和删除操作。然而，当数据规模极大或者节点连接非常密集时，字典的内存使用可能会成为问题。在这些情况下，可以考虑使用更为紧凑的数据结构如邻接表或邻接矩阵。对于极大规模的图，特别是分布式环境下，还可以考虑使用图数据库或分布式图处理框架（如Apache Spark的GraphX），这些技术可以更有效地在多机环境下处理大规模图数据。