Maximum Score After Applying Operations on a Tree

Med

#2605Time: 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).

Patterns

Dynamic Programming

Algorithms

Depth-First Search

Data structures

Tree

Prompt

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] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i 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 i^th 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:

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 * 10⁴
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
values.length == n
1 <= values[i] <= 10⁹
The input is generated such that edges represents a valid tree.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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).

1import java.util.ArrayList; 2import java.util.List;3 4class Solution {5    private List<List<Integer>> adj;6    private int[] values;7 8    public long maximumScoreAfterOperations(int[][] edges, int[] values) {9        int n = values.length;10        this.adj = new ArrayList<>();11        for (int i = 0; i < n; i++) {12            adj.add(new ArrayList<>());13        }14        for (int[] edge : edges) {15            adj.get(edge[0]).add(edge[1]);16            adj.get(edge[1]).add(edge[0]);17        }18        this.values = values;19 20        long totalSum = 0;21        for (int value : values) {22            totalSum += value;23        }24 25        long minUnpickedSum = dfs(0, -1);26        return totalSum - minUnpickedSum;27    }28 29    /**30     * Computes the minimum sum of values to leave in the subtree of u31     * to make all paths from u to its leaves healthy.32     */33    private long dfs(int u, int p) {34        long childrenSubtreeMinSum = 0;35        boolean isLeaf = true;36 37        for (int v : adj.get(u)) {38            if (v != p) {39                isLeaf = false;40                childrenSubtreeMinSum += dfs(v, u);41            }42        }43 44        // Base case: if the node is a leaf in the rooted tree traversal.45        if (isLeaf) {46            return (long)values[u];47        }48 49        // Recursive step: for an internal node, choose the minimum of two options.50        return Math.min((long)values[u], childrenSubtreeMinSum);51    }52}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

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:

1// This is a conceptual illustration and would be too slow to pass.2class BruteForceSolution {3    long maxScore = 0;4    int n;5    int[] values;6    List<List<Integer>> adj;7 8    public long solve(int[][] edges, int[] values) {9        // ... setup n, values, adj ...10        backtrack(0, new boolean[n]);11        return maxScore;12    }13 14    void backtrack(int u, boolean[] taken) {15        if (u == n) {16            if (isHealthy(taken)) {17                long currentScore = 0;18                for (int i = 0; i < n; i++) {19                    if (taken[i]) currentScore += values[i];20                }21                maxScore = Math.max(maxScore, currentScore);22            }23            return;24        }25 26        // Choice 1: Take node u27        taken[u] = true;28        backtrack(u + 1, taken);29 30        // Choice 2: Don't take node u31        taken[u] = false;32        backtrack(u + 1, taken);33    }34 35    boolean isHealthy(boolean[] taken) {36        // A helper DFS to check all root-to-leaf paths.37        // Returns true if all paths have a non-zero sum of untaken values.38        return checkPathHealth(0, -1, 0, taken);39    }40 41    boolean checkPathHealth(int u, int p, long currentPathSum, boolean[] taken) {42        long newPathSum = currentPathSum;43        if (!taken[u]) {44            newPathSum += values[u];45        }46 47        boolean isLeaf = true;48        for (int v : adj.get(u)) {49            if (v != p) {50                isLeaf = false;51                if (!checkPathHealth(v, u, newPathSum, taken)) {52                    return false; // An unhealthy path found in a subtree53                }54            }55        }56 57        if (isLeaf) {58            return newPathSum != 0;59        }60 61        return true;62    }63}

Complexity

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.

Trade-offs

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).

Solutions

Solution

1class Solution {2private3  List<Integer>[] g;4private5  int[] values;6public7  long maximumScoreAfterOperations(int[][] edges, int[] values) {8    int n = values.length;9    g = new List[n];10    this.values = values;11    Arrays.setAll(g, k->new ArrayList<>());12    for (var e : edges) {13      int a = e[0], b = e[1];14      g[a].add(b);15      g[b].add(a);16    }17    return dfs(0, -1)[1];18  }19private20  long[] dfs(int i, int fa) {21    long a = 0, b = 0;22    boolean leaf = true;23    for (int j : g[i]) {24      if (j != fa) {25        leaf = false;26        var t = dfs(j, i);27        a += t[0];28        b += t[1];29      }30    }31    if (leaf) {32      return new long[]{values[i], 0};33    }34    return new long[]{values[i] + a, Math.max(values[i] + b, a)};35  }36}

1class Solution {2public:3  long long maximumScoreAfterOperations(vector<vector<int>> &edges,4                                        vector<int> &values) {5    int n = values.size();6    vector<int> g[n];7    for (auto &e : edges) {8      int a = e[0], b = e[1];9      g[a].emplace_back(b);10      g[b].emplace_back(a);11    }12    using ll = long long;13    function<pair<ll, ll>(int, int)> dfs = [&](int i, int fa) -> pair<ll, ll> {14      ll a = 0, b = 0;15      bool leaf = true;16      for (int j : g[i]) {17        if (j != fa) {18          auto [aa, bb] = dfs(j, i);19          a += aa;20          b += bb;21          leaf = false;22        }23      }24      if (leaf) {25        return {values[i], 0LL};26      }27      return {values[i] + a, max(values[i] + b, a)};28    };29    auto [_, b] = dfs(0, -1);30    return b;31  }32};

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem