We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Score After Applying Operations on a Tree

Difficulty: Medium

Problem Description

There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. You are given a 2D integer array edges of length n - 1, where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree. You are also given a 0-indexed integer array values of length n, where values[i] is the value associated with the i-th node. You start with a score of 0. In one operation, you can:

  • Pick any node i.
  • Add values[i] to your score.
  • Set values[i] to 0.

A tree is healthy if the sum of values on the path from the root to any leaf node is different than zero. Return the maximum score you can obtain after performing these operations on the tree any number of times so that it remains healthy.

Key Insights

  • The tree is rooted at node 0, and we need to ensure that the path from the root to any leaf node does not sum to zero after performing operations.
  • Selecting leaf nodes is beneficial since their values directly contribute to the score without affecting other paths.
  • The root node can be included in the score only if it doesn't make the path to any leaf node sum to zero.
  • A depth-first search (DFS) approach can be used to traverse the tree and calculate the maximum score while keeping track of the paths.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a Depth-First Search (DFS) approach. We traverse the tree while maintaining the current score and checking the sums from the root to leaf nodes. We will store the maximum score possible while ensuring that paths to leaf nodes do not sum to zero.

  1. Construct the tree using an adjacency list from the edges.
  2. Perform a DFS starting from the root node:
    • For each node, add its value to the score if it doesn't lead to a zero-sum path to any leaf.
    • Recursively explore each child node, adjusting the current path sum.
    • Keep track of the maximum score obtained.

Code Solutions

def maxScore(edges, values):
    from collections import defaultdict

    # Create adjacency list
    tree = defaultdict(list)
    for a, b in edges:
        tree[a].append(b)
        tree[b].append(a)

    def dfs(node, parent, current_sum):
        current_sum += values[node]
        max_score = 0
        is_leaf = True
        
        for neighbor in tree[node]:
            if neighbor != parent:  # Avoid going back to parent
                is_leaf = False
                max_score = max(max_score, dfs(neighbor, node, current_sum))

        if is_leaf:  # If it's a leaf node
            return current_sum
        
        return max_score

    # Start DFS from the root node
    return dfs(0, -1, 0)

# Example usage
edges = [[0,1],[0,2],[0,3],[2,4],[4,5]]
values = [5,2,5,2,1,1]
print(maxScore(edges, values))  # Output: 11
← Back to All Questions