#2925

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Maximum Score After Applying Operations on a Tree

Solve Maximum Score After Applying Operations on a Tree by turning healthy-path constraints into subtree DP and forced-value tracking.

dynamic programming tree depth first search

Problem Statement

You are given a tree rooted at node 0, described by an undirected edge list and a value on every node. You may apply operations to chosen nodes to add their values to your score, but after all operations the tree must remain healthy, meaning every path from the root to any leaf still has a nonzero total value.

The optimization target is the maximum score you can collect while preserving that health condition. In the sample with edges [[0,1],[0,2],[0,3],[2,4],[4,5]] and values [5,2,5,2,1,1], the best result is 11 because leaving the root value untouched keeps every root-to-leaf path nonzero while allowing the other nodes to contribute to the score.

Examples

Example 1

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

Output: 11

We can choose nodes 1, 2, 3, 4, and 5. The value of the root is non-zero. Hence, the sum of values on the path from the root to any leaf is different than zero. Therefore, the tree is healthy and the score is values[1] + values[2] + values[3] + values[4] + values[5] = 11. It can be shown that 11 is the maximum score obtainable after any number of operations on the tree.

Example 2

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

Output: 40

We can choose nodes 0, 2, 3, and 4.

The sum of values on the path from 0 to 4 is equal to 10.
The sum of values on the path from 0 to 3 is equal to 10.
The sum of values on the path from 0 to 5 is equal to 3.
The sum of values on the path from 0 to 6 is equal to 5. Therefore, the tree is healthy and the score is values[0] + values[2] + values[3] + values[4] = 40. It can be shown that 40 is the maximum score obtainable after any number of operations on the tree.

Constraints

2 <= n <= 2 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
values.length == n
1 <= values[i] <= 109
The input is generated such that edges represents a valid tree.

Solution Approach

Reframe the score as kept value

Instead of maximizing removed score directly, compute the minimum value that must stay in each subtree. Let subtreeSum[u] be the sum of values in node u's subtree, and let dp[u] be the minimum value that must remain there so every path from u to a leaf still has a nonzero sum. The answer becomes totalSum - dp[0].

Use DFS with a leaf base case

Build an adjacency list and run DFS from the root with a parent pointer. For a leaf, dp[u] must equal values[u] because if you remove that leaf completely, the path ending there becomes zero. During the same DFS, accumulate subtreeSum[u] by adding child subtree sums.

Apply the subtree transition carefully

For a non-leaf node u, there are two valid ways to keep the subtree healthy. One option is to keep the entire subtree sum, which corresponds to never relying on child structure savings. The better option is to keep values from children just enough to satisfy each child subtree, which costs sum of dp[child]. Therefore dp[u] = min(subtreeSum[u], sum(dp[child])). This transition is the core trade-off: a node with large value may be removed if its children already force enough remaining value, but a leaf can never drop to zero.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The DFS visits each node and edge once, so the time complexity is O(n). The adjacency list, recursion stack, subtree sums, and dp storage use O(n) space. With n up to 2 * 10^4, this linear tree DP is the intended fit.

What Interviewers Usually Probe

They want you to convert a global healthy-path rule into a local subtree DP state.
They expect you to notice that maximizing score is equivalent to minimizing the value that must remain.
They are testing whether you can write a parent-aware DFS on an undirected tree without revisiting nodes.

Common Pitfalls or Variants

Common pitfalls

Treating this as a greedy pick-the-largest-values problem and breaking a leaf path by removing its only remaining value.
Using the wrong base case for leaves; dp[leaf] is values[leaf], not 0.
Forgetting that the graph is undirected and recursing back to the parent, which corrupts subtree sums and causes cycles.

Follow-up variants

Return the minimum value that must remain instead of the maximum score; that is exactly dp[0].
Change the healthy rule so every root-to-leaf path must stay at least K, which would alter the subtree state and transition.
Ask for an iterative postorder traversal version to avoid recursion depth concerns on a long chain tree.

FAQ

What is the main idea in Maximum Score After Applying Operations on a Tree?

Compute the minimum value that must stay in the tree to keep every root-to-leaf path nonzero, then subtract that from the total sum. This turns the problem into a DFS plus subtree DP.

Why is the leaf case so important in this problem?

A leaf path contains no deeper node to rescue it. If a leaf subtree kept value becomes 0, that entire root-to-leaf path can become zero, so dp at a leaf must equal the leaf's own value.

Why does the transition use min(subtreeSum, sum of child dp values)?

Keeping subtreeSum means preserving everything under that node. Keeping sum of child dp values means removing the current node's value and relying on each child subtree to preserve just enough value, so you take the cheaper valid option.

Is this really a binary-tree traversal and state tracking problem?

The pattern is broader than binary trees because the input tree can have any number of children. The useful part of the hint is state tracking during postorder traversal: each node combines child states and subtree sums.

Can this be solved greedily or with a simple path check?

No, because a choice at one node changes what every descendant path is allowed to lose. The dependency is subtree-wide, which is why the DP state per node is needed instead of local greedy decisions.

terminal

Solution

Solution 1: Tree DP

The problem is actually asking us to select some nodes from all nodes of the tree so that the sum of these nodes' values is maximized, and there is one node on each path from the root node to the leaf node that is not selected.

class Solution:
    def maximumScoreAfterOperations(
        self, edges: List[List[int]], values: List[int]
    ) -> int:
        def dfs(i: int, fa: int = -1) -> (int, int):
            a = b = 0
            leaf = True
            for j in g[i]:
                if j != fa:
                    leaf = False
                    aa, bb = dfs(j, i)
                    a += aa
                    b += bb
            if leaf:
                return values[i], 0
            return values[i] + a, max(values[i] + b, a)

        g = [[] for _ in range(len(values))]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        return dfs(0)[1]

Continue Practicing

#2920 maximum points after collecting coins from all nodes #2973 find number of coins to place in tree nodes #2867 count valid paths in a tree