# Maximum Score After Applying Operations on a Tree **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-score-after-applying-operations-on-a-tree) Canonical: https://scaleengineer.com/dsa/problems/maximum-score-after-applying-operations-on-a-tree **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search) **Data structures:** Tree --- ## Problem 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: * 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**._ **Example 1:** ![](https://assets.glich.co/dsa/maximum-score-after-applying-operations-on-a-tree/image0.png) **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:** ![](https://assets.glich.co/dsa/maximum-score-after-applying-operations-on-a-tree/image1.png) **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 * 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. # Approaches ## Brute Force via Backtracking This approach considers all possibilities. For each of the `n` nodes, we have two choices: either take its value (add to score, value becomes 0) or leave it. This gives `2^n` total combinations. For each combination, we check if the resulting tree is 'healthy'. A tree is healthy if every path from the root to a leaf has a non-zero sum of values. If it is, we calculate the score and keep track of the maximum score found. **Time:** O(n * 2^n). There are `2^n` possible ways to take/leave nodes. For each way, we perform an `O(n)` check for healthiness. · **Space:** O(n) for the recursion stack depth and the `taken` array. **Pros:** Guaranteed to find the correct answer.; Relatively straightforward to conceptualize. **Cons:** Extremely inefficient due to its exponential time complexity.; Not feasible for the given constraints on `n` (up to 2 * 10^4). ### Explanation A brute-force solution can be implemented using backtracking. We can define a recursive function that iterates through each node from `0` to `n-1` and makes a decision for each: either take its value or not. When the recursive function reaches its base case (all nodes decided), it triggers a validation check on the entire tree. This check verifies the 'healthy' condition. A separate DFS traversal can perform this check efficiently in `O(n)` time. This DFS would traverse from the root, keeping track of the sum of values of untaken nodes along the current path. When it reaches a leaf, it checks if this path sum is zero. If it is, the configuration is invalid. If all root-to-leaf paths have non-zero sums, the configuration is valid. If valid, we compute the score and update a global maximum. While correct, this method is computationally prohibitive. Here is a conceptual sketch of the backtracking logic: ```java // This is a conceptual illustration and would be too slow to pass. class BruteForceSolution { long maxScore = 0; int n; int[] values; List> adj; public long solve(int[][] edges, int[] values) { // ... setup n, values, adj ... backtrack(0, new boolean[n]); return maxScore; } void backtrack(int u, boolean[] taken) { if (u == n) { if (isHealthy(taken)) { long currentScore = 0; for (int i = 0; i < n; i++) { if (taken[i]) currentScore += values[i]; } maxScore = Math.max(maxScore, currentScore); } return; } // Choice 1: Take node u taken[u] = true; backtrack(u + 1, taken); // Choice 2: Don't take node u taken[u] = false; backtrack(u + 1, taken); } boolean isHealthy(boolean[] taken) { // A helper DFS to check all root-to-leaf paths. // Returns true if all paths have a non-zero sum of untaken values. return checkPathHealth(0, -1, 0, taken); } boolean checkPathHealth(int u, int p, long currentPathSum, boolean[] taken) { long newPathSum = currentPathSum; if (!taken[u]) { newPathSum += values[u]; } boolean isLeaf = true; for (int v : adj.get(u)) { if (v != p) { isLeaf = false; if (!checkPathHealth(v, u, newPathSum, taken)) { return false; // An unhealthy path found in a subtree } } } if (isLeaf) { return newPathSum != 0; } return true; } } ``` ### Algorithm - The core idea is to explore every possible combination of taking or not taking each node's value. - We can use a recursive backtracking function to generate all `2^n` subsets of nodes. - The function, say `backtrack(index, taken_mask)`, would decide for `nodes[index]` whether to take its value or not, and then recurse for `index + 1`. - The base case for the recursion is when all nodes have been decided (`index == n`). - In the base case, we have a complete configuration of taken/untaken nodes. We must then verify if this configuration results in a 'healthy' tree. - To check if the tree is healthy, we perform a traversal (like DFS) from the root. For every path to a leaf, we sum the values of the nodes that were *not* taken. If any such path sum is zero, the tree is unhealthy for this configuration. - If the tree is healthy, we calculate the score for the current configuration (sum of values of all taken nodes) and update our global maximum score if it's higher. - This process guarantees finding the maximum score because it exhaustively checks all possibilities. ## Dynamic Programming on Tree A more efficient approach uses dynamic programming on the tree. The key insight is to reframe the problem: instead of maximizing the score of nodes we take, we can minimize the sum of values of nodes we *don't* take. The 'healthy' condition requires that on every path from the root to a leaf, at least one node's value must be left untouched. This structure lends itself to a post-order traversal (DFS) where for each node, we compute the minimum value that must be left in its subtree to satisfy the healthy condition for all paths starting from that node. This avoids re-computation and explores the decision space efficiently. **Time:** O(n). We visit each node and edge once to build the adjacency list, and once during the DFS traversal. Summing the initial values also takes O(n). · **Space:** O(n) for storing the adjacency list and for the recursion stack in the worst-case scenario (a skewed tree). **Pros:** Optimal time complexity of O(n).; Efficiently solves the problem for large inputs.; Elegant solution based on a clear recurrence relation. **Cons:** Requires recognizing the problem can be transformed and solved with tree DP.; Slightly more complex to implement than a naive brute-force approach. ### Explanation We can solve this problem optimally in linear time using a single DFS traversal. Let's define `dfs(u, p)` as a function that computes the minimum sum of values that must be left in the subtree rooted at `u` (with `p` being its parent) to ensure that any path from `u` to a leaf in its subtree has a non-zero sum. - **For a leaf node `u`:** The only path is the node itself. We must leave its value. So, `dfs(u, p)` returns `values[u]`. - **For an internal node `u`:** We have two options: 1. **Leave `values[u]`:** The cost incurred is `values[u]`. Since `u` is on every path starting from itself, this single choice makes all paths from `u` to its descendant leaves healthy. 2. **Take `values[u]`:** We don't leave `values[u]`. To maintain the healthy property, we must now ensure it's satisfied in the subtrees of its children. Since the subtrees are independent, we must pay the minimum cost for each child's subtree. The total cost is the sum of the results of `dfs(v, u)` for all children `v` of `u`. We choose the option with the minimum cost. Thus, for an internal node `u`, `dfs(u, p) = min(values[u], sum(dfs(v, u)))` for all children `v`. The final answer is the total sum of all values in the tree minus the minimum cost for the entire tree, which is `dfs(0, -1)`. ```java import java.util.ArrayList; import java.util.List; class Solution { private List> adj; private int[] values; public long maximumScoreAfterOperations(int[][] edges, int[] values) { int n = values.length; this.adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } this.values = values; long totalSum = 0; for (int value : values) { totalSum += value; } long minUnpickedSum = dfs(0, -1); return totalSum - minUnpickedSum; } /** * Computes the minimum sum of values to leave in the subtree of u * to make all paths from u to its leaves healthy. */ private long dfs(int u, int p) { long childrenSubtreeMinSum = 0; boolean isLeaf = true; for (int v : adj.get(u)) { if (v != p) { isLeaf = false; childrenSubtreeMinSum += dfs(v, u); } } // Base case: if the node is a leaf in the rooted tree traversal. if (isLeaf) { return (long)values[u]; } // Recursive step: for an internal node, choose the minimum of two options. return Math.min((long)values[u], childrenSubtreeMinSum); } } ``` ### Algorithm - The problem of maximizing the score of taken nodes is equivalent to minimizing the sum of values of nodes that are left untouched, subject to the 'healthy' constraint. - The healthy constraint means that for every root-to-leaf path, at least one node must be left untouched. - We can define a function, `minCost(u)`, which represents the minimum sum of values we must leave in the subtree rooted at `u` to ensure all paths from `u` to leaves within its subtree are 'healthy'. - We can compute `minCost(u)` using a post-order traversal (DFS). - **Base Case:** For a leaf node `u`, the only path in its subtree is the node itself. To make this path healthy, we must leave `values[u]`. So, `minCost(u) = values[u]`. - **Recursive Step:** For an internal node `u`, we have two choices: 1. Leave `values[u]`. The cost is `values[u]`. This satisfies the condition for all paths from `u` downwards. 2. Take `values[u]`. Now, for each child `v` of `u`, we must satisfy the condition within `v`'s subtree. The total cost for this choice is the sum of `minCost(v)` for all children `v`. - The recurrence relation is `minCost(u) = min(values[u], sum(minCost(v) for v in children(u)))`. - First, calculate the total sum of all values in the tree. - Then, run the DFS from the root (node 0) to compute `minCost(0)`. - The final maximum score is `totalSum - minCost(0)`. # Solutions ### Java ```java class Solution { private List[] g; private int[] values; public long maximumScoreAfterOperations(int[][] edges, int[] values) { int n = values.length; g = new List[n]; this.values = values; Arrays.setAll(g, k->new ArrayList<>()); for (var e : edges) { int a = e[0], b = e[1]; g[a].add(b); g[b].add(a); } return dfs(0, -1)[1]; } private long[] dfs(int i, int fa) { long a = 0, b = 0; boolean leaf = true; for (int j : g[i]) { if (j != fa) { leaf = false; var t = dfs(j, i); a += t[0]; b += t[1]; } } if (leaf) { return new long[]{values[i], 0}; } return new long[]{values[i] + a, Math.max(values[i] + b, a)}; } } ``` ### CPP ```cpp class Solution { public: long long maximumScoreAfterOperations(vector> &edges, vector &values) { int n = values.size(); vector g[n]; for (auto &e : edges) { int a = e[0], b = e[1]; g[a].emplace_back(b); g[b].emplace_back(a); } using ll = long long; function(int, int)> dfs = [&](int i, int fa) -> pair { ll a = 0, b = 0; bool leaf = true; for (int j : g[i]) { if (j != fa) { auto [aa, bb] = dfs(j, i); a += aa; b += bb; leaf = false; } } if (leaf) { return {values[i], 0LL}; } return {values[i] + a, max(values[i] + b, a)}; }; auto [_, b] = dfs(0, -1); return b; } }; ``` ### Python ```python 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] ```