2925. Maximum Score After Applying Operations on a Tree LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2925. Maximum Score After Applying Operations on a Tree LeetCode Solution with the best time and space complexity. The solution to Maximum Score After Applying Operations on a Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Score After Applying Operations on a Tree solution in C++
Maximum Score After Applying Operations on a Tree solution in Java
Maximum Score After Applying Operations on a Tree solution in Python
Additional Resources

2925. Maximum Score After Applying Operations on a Tree LeetCode Solution image

Problem Statement of Maximum Score After Applying Operations on a Tree

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:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2925. Maximum Score After Applying Operations on a Tree LeetCode Solution in C++

class Solution {
 public:
  long long maximumScoreAfterOperations(vector<vector<int>>& edges,
                                        vector<int>& values) {
    vector<vector<int>> tree(values.size());

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      tree[u].push_back(v);
      tree[v].push_back(u);
    }

    return accumulate(values.begin(), values.end(), 0L) -
           dfs(tree, 0, /*prev=*/-1, values);
  }

 private:
  // Returns the minimum of sum to be reduced.
  long dfs(const vector<vector<int>>& tree, int u, int prev,
           const vector<int>& values) {
    if (u > 0 && tree[u].size() == 1)
      return values[u];
    long childrenSum = 0;
    for (const int v : tree[u])
      if (v != prev)
        childrenSum += dfs(tree, v, u, values);
    return min(childrenSum, static_cast<long>(values[u]));
  }
};
/* code provided by PROGIEZ */

2925. Maximum Score After Applying Operations on a Tree LeetCode Solution in Java

class Solution {
  public long maximumScoreAfterOperations(int[][] edges, int[] values) {
    List<Integer>[] tree = new ArrayList[values.length];

    for (int i = 0; i < values.length; ++i)
      tree[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      tree[u].add(v);
      tree[v].add(u);
    }

    return Arrays.stream(values).sum() - dfs(tree, 0, /*prev=*/-1, values);
  }

  private long dfs(List<Integer>[] tree, int u, int prev, int[] values) {
    if (u > 0 && tree[u].size() == 1)
      return values[u];
    long childrenSum = 0;
    for (final int v : tree[u])
      if (v != prev)
        childrenSum += dfs(tree, v, u, values);
    return Math.min(childrenSum, 1L * values[u]);
  }
}
// code provided by PROGIEZ

2925. Maximum Score After Applying Operations on a Tree LeetCode Solution in Python

class Solution:
  def maximumScoreAfterOperations(
      self,
      edges: list[list[int]],
      values: list[int],
  ) -> int:
    tree = [[] for _ in values]

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

    def dfs(u: int, prev: int) -> None:
      if u > 0 and len(tree[u]) == 1:
        return values[u]
      childrenSum = sum(dfs(v, u)
                        for v in tree[u]
                        if v != prev)
      return min(childrenSum, values[u])

    return sum(values) - dfs(0, -1)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents