LeetCode 2925 - Maximum Score After Applying Operations on a Tree

The problem gives us an undirected tree with n nodes rooted at node 0. Every node has an associated positive value. We may repeatedly perform an operation where we choose a node, add its current value to our score, and then permanently set that node's value to 0.

leetcodemediumdynamic-programmingtreedepth-first-search

LeetCode Problem 2925

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Tree, Depth-First Search

Solution

Problem Understanding

The problem gives us an undirected tree with n nodes rooted at node 0. Every node has an associated positive value. We may repeatedly perform an operation where we choose a node, add its current value to our score, and then permanently set that node's value to 0.

However, after all operations are complete, the tree must remain "healthy".

A tree is considered healthy if, for every root-to-leaf path, the sum of node values along that path is not equal to zero.

Since all original values are positive, the only way a path can become zero is if every node on that path has been set to 0. Therefore, for every root-to-leaf path, at least one node must remain untouched.

The goal is to maximize the total score collected.

Another way to think about the problem is this:

  • We want to remove as many node values as possible.
  • But every root-to-leaf path must retain at least one positive node.

This transforms the problem into a tree dynamic programming problem.

The input consists of:

  • edges, describing the tree structure
  • values, where values[i] is the value stored at node i

The output is the maximum total score obtainable while preserving the healthy condition.

The constraints are important:

  • n can be as large as 2 * 10^4
  • Values can be up to 10^9

This immediately rules out exponential or quadratic solutions over all subsets of nodes. Since the input is a tree, we should expect a DFS-based dynamic programming solution with linear complexity.

Several edge cases are important:

  • A single leaf child under the root
  • Deep chain-like trees
  • Star-shaped trees
  • Situations where keeping one expensive node is better than keeping many smaller nodes
  • Leaf nodes, because removing a leaf may invalidate an entire root-to-leaf path

The problem guarantees the graph is a valid tree, meaning:

  • Connected
  • Exactly n - 1 edges
  • No cycles

This allows standard DFS traversal without worrying about disconnected components.

Approaches

Brute Force Approach

A brute force solution would try every possible subset of nodes to remove.

For each subset:

  1. Set those nodes to zero
  2. Compute every root-to-leaf path sum
  3. Verify that no path sum equals zero
  4. Track the maximum removable value

This works because it explicitly checks all valid configurations.

However, there are 2^n possible subsets of nodes. Even for n = 30, this becomes infeasible. With n = 2 * 10^4, brute force is completely impossible.

The core issue is that the decision at one node affects all paths passing through that node. Exhaustively checking all combinations wastes enormous work.

Key Insight

Instead of deciding which nodes to remove globally, we can solve the problem recursively on subtrees.

Observe the following:

  • Every root-to-leaf path must retain at least one node.

  • For any subtree, we either:

  • Keep the current node

  • Or ensure every child subtree independently remains healthy

Suppose we are processing node u.

Let:

  • subtree_sum(u) = total value of all nodes in the subtree rooted at u
  • cost(u) = minimum value that must remain in the subtree to keep it healthy

If we know the minimum value we must preserve, then:

maximum removable score = total_sum - minimum_preserved

For a leaf node:

  • We must keep that node
  • Otherwise the single root-to-leaf path becomes zero

So:

cost(leaf) = values[leaf]

For an internal node:

We have two choices:

  1. Keep node u
  • Cost = values[u]
  1. Remove node u
  • Then every child subtree must independently stay healthy
  • Cost = sum of child costs

Therefore:

cost(u) = min(values[u], sum(child_costs))

This gives a clean DFS dynamic programming solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Tries every subset of removed nodes
Optimal DFS DP O(n) O(n) Computes minimum preserved value using tree DP

Algorithm Walkthrough

Step 1: Build the adjacency list

Since the input is an undirected tree, we first convert the edge list into an adjacency list.

This allows efficient DFS traversal.

Step 2: Compute total tree sum

We calculate:

total_sum = sum(values)

Our final answer will be:

total_sum - minimum_preserved

So the DFS only needs to determine the minimum amount that must remain.

Step 3: Run DFS from the root

We perform DFS starting from node 0.

The DFS function returns:

minimum value that must remain in this subtree

Step 4: Handle leaf nodes

A leaf node has no children except its parent.

If we remove a leaf node, then the root-to-leaf path ending there becomes entirely zero.

Therefore we must keep the leaf.

So:

dfs(leaf) = values[leaf]

Step 5: Process internal nodes

For an internal node u, recursively compute child costs.

Let:

child_cost_sum = sum(dfs(child))

Now we decide:

  • Keep current node:

  • preserve values[u]

  • Remove current node:

  • preserve enough inside every child subtree

Therefore:

dfs(u) = min(values[u], child_cost_sum)

Step 6: Compute final answer

After DFS completes:

minimum_preserved = dfs(0)

The maximum removable score is:

total_sum - minimum_preserved

Return this value.

Why it works

For every subtree, the DFS computes the minimum amount of value that must remain so that every root-to-leaf path inside that subtree still contains at least one non-zero node.

At each node, we optimally choose between:

  • Preserving the current node itself
  • Removing it and forcing all child subtrees to preserve enough nodes independently

Because every subtree is solved optimally and independently, the recursion guarantees a globally optimal solution.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:
        n = len(values)

        graph = defaultdict(list)

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        total_sum = sum(values)

        def dfs(node: int, parent: int) -> int:
            children = 0
            child_cost_sum = 0

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                children += 1
                child_cost_sum += dfs(neighbor, node)

            # Leaf node
            if children == 0:
                return values[node]

            return min(values[node], child_cost_sum)

        minimum_preserved = dfs(0, -1)

        return total_sum - minimum_preserved

The implementation begins by building an adjacency list for the tree. Since the graph is undirected, each edge is inserted in both directions.

Next, the total sum of all node values is computed. This represents the maximum possible score if every node could be removed.

The DFS function is the core of the algorithm. It recursively computes the minimum value that must remain in each subtree.

Inside the DFS:

  • We skip the parent node to avoid revisiting nodes
  • We count children to identify leaves
  • We accumulate the minimum preserved costs from child subtrees

If a node has no children, it is a leaf and must remain non-zero, so its cost equals its own value.

For internal nodes, we choose the cheaper option between:

  • Preserving the current node
  • Preserving enough among child subtrees

Finally, the minimum preserved value at the root is subtracted from the total sum to obtain the maximum score.

Go Solution

package main

func maximumScoreAfterOperations(edges [][]int, values []int) int64 {
	n := len(values)

	graph := make([][]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	var totalSum int64

	for _, value := range values {
		totalSum += int64(value)
	}

	var dfs func(int, int) int64

	dfs = func(node int, parent int) int64 {
		children := 0
		var childCostSum int64

		for _, neighbor := range graph[node] {
			if neighbor == parent {
				continue
			}

			children++
			childCostSum += dfs(neighbor, node)
		}

		// Leaf node
		if children == 0 {
			return int64(values[node])
		}

		nodeValue := int64(values[node])

		if nodeValue < childCostSum {
			return nodeValue
		}

		return childCostSum
	}

	minimumPreserved := dfs(0, -1)

	return totalSum - minimumPreserved
}

The Go implementation follows the same recursive DP structure as the Python version.

A few Go-specific details are important:

  • The result type is int64 because sums can exceed 32-bit integer limits
  • Slices are used for adjacency lists
  • Recursive DFS is implemented using a function variable declaration
  • Integer conversions to int64 are necessary during arithmetic operations

The logic itself remains identical to the Python solution.

Worked Examples

Example 1

Input:

edges = [[0,1],[0,2],[0,3],[2,4],[4,5]]
values = [5,2,5,2,1,1]

Tree structure:

        0(5)
      /  |  \
   1(2) 2(5) 3(2)
          |
         4(1)
          |
         5(1)

Total sum:

5 + 2 + 5 + 2 + 1 + 1 = 16

DFS processing happens bottom-up.

Node Child Costs Node Value Result
1 none 2 2
5 none 1 1
4 1 1 min(1,1)=1
2 1 5 min(5,1)=1
3 none 2 2
0 2+1+2=5 5 min(5,5)=5

Minimum preserved value:

5

Maximum score:

16 - 5 = 11

Answer:

11

Example 2

Input:

edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
values = [20,10,9,7,4,3,5]

Tree:

           0(20)
         /       \
      1(10)      2(9)
      /   \      /   \
   3(7) 4(4) 5(3) 6(5)

Total sum:

20 + 10 + 9 + 7 + 4 + 3 + 5 = 58

DFS evaluation:

Node Child Costs Node Value Result
3 none 7 7
4 none 4 4
1 7+4=11 10 10
5 none 3 3
6 none 5 5
2 3+5=8 9 8
0 10+8=18 20 18

Minimum preserved:

18

Maximum score:

58 - 18 = 40

Answer:

40

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node and edge is visited once
Space O(n) Adjacency list and recursion stack

The DFS traverses the tree exactly once. Since a tree with n nodes has n - 1 edges, the total traversal cost is linear.

The adjacency list requires O(n) space, and the recursion stack may also reach O(n) in the worst case of a skewed tree.

Test Cases

from typing import List

class Solution:
    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:
        from collections import defaultdict

        graph = defaultdict(list)

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        total_sum = sum(values)

        def dfs(node: int, parent: int) -> int:
            children = 0
            child_sum = 0

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                children += 1
                child_sum += dfs(neighbor, node)

            if children == 0:
                return values[node]

            return min(values[node], child_sum)

        return total_sum - dfs(0, -1)

sol = Solution()

# Example 1
assert sol.maximumScoreAfterOperations(
    [[0,1],[0,2],[0,3],[2,4],[4,5]],
    [5,2,5,2,1,1]
) == 11  # basic mixed tree

# Example 2
assert sol.maximumScoreAfterOperations(
    [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]],
    [20,10,9,7,4,3,5]
) == 40  # balanced binary tree

# Smallest valid tree
assert sol.maximumScoreAfterOperations(
    [[0,1]],
    [1,2]
) == 2  # must preserve one node on path

# Chain tree
assert sol.maximumScoreAfterOperations(
    [[0,1],[1,2],[2,3]],
    [1,2,3,4]
) == 9  # preserve cheapest possible node

# Star-shaped tree
assert sol.maximumScoreAfterOperations(
    [[0,1],[0,2],[0,3]],
    [10,1,1,1]
) == 3  # best to preserve root

# Large root value
assert sol.maximumScoreAfterOperations(
    [[0,1],[1,2]],
    [100,1,1]
) == 101  # preserve small subtree instead of root

# Equal costs
assert sol.maximumScoreAfterOperations(
    [[0,1],[0,2]],
    [5,5,5]
) == 5  # either choice gives same result

# Deep skewed tree
assert sol.maximumScoreAfterOperations(
    [[0,1],[1,2],[2,3],[3,4]],
    [5,4,3,2,1]
) == 14  # preserve only minimum path value

Test Summary

Test Why
Example 1 Validates mixed-depth tree
Example 2 Validates balanced tree decisions
Smallest valid tree Tests minimum input size
Chain tree Tests deep recursion behavior
Star-shaped tree Tests preserving root vs leaves
Large root value Tests optimal subtree preservation
Equal costs Tests tie situations
Deep skewed tree Tests worst-case recursion depth

Edge Cases

One important edge case is a leaf node. A leaf represents the end of a root-to-leaf path. If we remove the leaf and every ancestor on that path is also removed, the path sum becomes zero. The implementation handles this by forcing leaf nodes to return their own value as the minimum preserved cost.

Another important edge case is a skewed tree that behaves like a linked list. In such cases, recursive depth becomes large, and incorrect parent handling could cause infinite recursion. The implementation avoids revisiting the parent node during DFS, ensuring correct traversal without cycles.

A third important case occurs when an internal node's value is much larger than the combined preservation costs of its children. In this situation, it is better to remove the internal node and preserve enough value among descendants instead. The recurrence:

min(values[node], child_cost_sum)

correctly chooses the cheaper option.

A final subtle edge case happens when preserving the current node and preserving child subtrees cost exactly the same amount. The algorithm still works correctly because either choice preserves the health condition while achieving the same optimal score.