Watch 10 video solutions for Maximum Score After Applying Operations on a Tree, a medium level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by Ayush Rao has 1,830 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] = [ai, bi] indicates that there is an edge between nodes ai and bi 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 ith node.
You start with a score of 0. In one operation, you can:
i.values[i] to your score.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.
Example 1:
Input: edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1] Output: 11 Explanation: 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 Explanation: 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 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < nvalues.length == n1 <= values[i] <= 109edges represents a valid tree.Problem Overview: You are given a tree where each node has a value. You may apply operations that collect a node’s value into the score and set that node to zero. After all operations, every root-to-leaf path must still have a non-zero total. The goal is to maximize the score collected.
Approach 1: DFS with Tree Dynamic Programming (O(n) time, O(n) space)
The key observation: instead of directly maximizing the score, compute the minimum value that must remain in the tree so every root-to-leaf path keeps a positive sum. If you know the total sum of all node values, the final score is simply totalSum - requiredSum. Use Depth-First Search to process the tree bottom‑up. For a leaf node, you must keep its value because removing it would make the path sum zero. For an internal node, you have a choice: keep the node’s value, or rely on its children to keep enough value in the subtree. Therefore the minimum required value at a node is min(nodeValue, sum(childRequired)). This recursive decision naturally forms a Dynamic Programming state on the tree. Traverse the tree, compute the required value for each subtree, and subtract the root’s required value from the total sum.
Approach 2: Iterative DFS Using Stack (O(n) time, O(n) space)
The same DP logic can be implemented iteratively to avoid recursion depth limits. Build an adjacency list and simulate post‑order traversal with a stack. Each stack frame tracks whether children have been processed. Once all children of a node are evaluated, compute its required value using the same rule: leaf nodes return their value, while internal nodes return min(nodeValue, sum(childRequired)). Store intermediate results in an array or map indexed by node. This approach is useful in environments where recursion depth may exceed limits or when you prefer explicit control over traversal.
Recommended for interviews: The recursive DFS with tree DP is the expected solution. It runs in linear time, clearly models the constraint that each path must retain value, and demonstrates comfort with tree-based dynamic programming. Mentioning the iterative DFS variant shows awareness of stack-based traversal and recursion limits.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Tree Dynamic Programming | O(n) | O(n) | Best general solution. Clean recursive logic and optimal performance. |
| Iterative DFS using Stack | O(n) | O(n) | Useful when recursion depth may overflow or when iterative traversal is preferred. |