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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Score After Applying Operations on a Tree

Number: 3191

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an undirected tree with n nodes (labeled from 0 to n-1) rooted at node 0, each node has a positive integer value given by the array values. In one operation you pick a node i, add its value to your score, and set its value to 0. You may perform this operation any number of times under the constraint that the tree remains "healthy" – meaning that the sum of the values that remain along the path from the root to any leaf is not zero. Return the maximum score that can be obtained.

Effectively, when you “pick” (or remove) a node, you collect its value, but that node no longer contributes to the sum along any root-to-leaf path. To keep the tree healthy, every root-to-leaf path must contain at least one node that is not picked.

Key Insights

  • The problem can be reframed as: remove as many nodes as possible (collecting their values) while leaving a set of nodes (the “guard” nodes) that cover every root-to-leaf path.
  • Since every node’s value is positive, to maximize the score, you want to remove nodes with large values and leave behind a set of nodes with the minimum total value such that every root-to-leaf path has at least one kept node.
  • The maximum score is equal to the total sum of node values minus the minimum sum of nodes that must be kept.
  • For a node u whose subtree must have at least one kept node (i.e. if no guard exists from an ancestor), you have two choices: • Keep u (incurring cost values[u]), or
    • Remove u and force that its children’s subtrees cover the “guard” condition.
  • Using a DFS based dynamic programming solution on the tree we define a function f(u) that represents the minimum sum cost of keeping nodes in the subtree rooted at u when there is NO guard provided from above. For a leaf node, f(u) must equal values[u] (it must be kept when there is no guard above).
  • Therefore, for an internal node u, f(u) = min( values[u], Σ f(child) ) and the answer becomes MaxScore = (total sum of values) − f(root).

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes (each node is visited once during DFS). Space Complexity: O(n) for the recursion stack and the tree representation.

Solution

We solve the problem by converting it to a minimization problem. Instead of explicitly choosing nodes to remove, we decide which nodes to keep such that every root-to-leaf path contains at least one kept node. The total score we obtain is the sum of all removed node values, which is equal to the total sum of node values minus the sum of kept node values. To minimize the sum of kept node values, we use DFS dynamic programming.

For each node u:

  1. If u is a leaf, it must be kept (to cover its own path) and f(u) = values[u].
  2. If u is not a leaf, we have two options:
    • Keep u: cost = values[u] (and then the children need no additional guarding, so they can all be removed).
    • Do not keep u: then every child's subtree must independently have a guard, i.e., we must add Σ f(child).
  3. Hence, f(u) = min( values[u], Σ f(child) ). The answer is totalSum − f(root).

Code Solutions

# Python solution with detailed comments

def maxScoreAfterOperations(edges, values):
    # Build the tree as an adjacency list.
    n = len(values)
    tree = [[] for _ in range(n)]
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    # Use DFS to compute the minimum cost of kept nodes for each subtree.
    # f(u): minimal cost required in subtree rooted at u when no guard exists from ancestors.
    def dfs(u, parent):
        # Determine if current node is a leaf in the DFS tree.
        # (Leaf: has no child other than its parent.)
        is_leaf = True
        total_children_cost = 0
        for v in tree[u]:
            if v == parent:
                continue
            is_leaf = False
            total_children_cost += dfs(v, u)
        # If u is a leaf, it must be kept, so return its value.
        if is_leaf:
            return values[u]
        # Option 1: Keep u, with cost = values[u].
        # Option 2: Do not keep u, then children must cover the guard condition, cost = total cost from children.
        return min(values[u], total_children_cost)
    
    total_sum = sum(values)
    min_kept = dfs(0, -1)
    return total_sum - min_kept

# Example usage:
edges1 = [[0,1],[0,2],[0,3],[2,4],[4,5]]
values1 = [5,2,5,2,1,1]
print(maxScoreAfterOperations(edges1, values1))  # Expected output: 11
← Back to All Questions