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

Master LeetCode problem 2925 (Maximum Score After Applying Operations on a Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2925. Maximum Score After Applying Operations on a Tree

Medium

Dynamic Programming Tree Depth-First Search

Problem Explanation

Explanation

To solve this problem, we can perform a depth-first search (DFS) starting from the root node (node 0). During the traversal, we calculate the maximum score we can achieve by either including the current node in the path or excluding it. We keep track of two values for each node - maxInclude which represents the maximum score when including the current node in the path, and maxExclude which represents the maximum score when excluding the current node.

For each node, we recursively calculate the maximum scores for its child nodes. We update the maxInclude and maxExclude values based on the values obtained from the child nodes. When considering a node, we have two options:

Include the current node: In this case, we add the value of the current node to the score and recursively calculate the maximum scores for its child nodes with the constraint that the current node's value is set to 0 after considering it.
Exclude the current node: In this case, we do not add the value of the current node to the score, but we still recursively calculate the maximum scores for its child nodes.

The final answer will be the maximum of the maxInclude and maxExclude values for the root node.

Time Complexity

The time complexity of this approach is O(N), where N is the number of nodes in the tree.

Space Complexity

The space complexity is also O(N) due to the recursion stack.

Solution Code

class Solution {
    public int maxScore(int[] values, int[][] edges) {
        // Define a helper function to perform DFS
        // Return an array where [0] is maxInclude and [1] is maxExclude
        int[] dfs(int node, List<List<Integer>> adjList, boolean[] visited, int[] values) {
            visited[node] = true;
            int[] result = new int[]{values[node], 0};
            for (int child : adjList.get(node)) {
                if (!visited[child]) {
                    int[] childResult = dfs(child, adjList, visited, values);
                    result[1] += Math.max(childResult[0], childResult[1]);
                    result[0] += childResult[1];
                }
            }
            return result;
        }
        
        int n = values.length;
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }
        
        boolean[] visited = new boolean[n];
        int[] result = dfs(0, adjList, visited, values);
        
        return Math.max(result[0], result[1]);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2925 (Maximum Score After Applying Operations on a Tree)?

This page provides optimized solutions for LeetCode problem 2925 (Maximum Score After Applying Operations on a Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2925 (Maximum Score After Applying Operations on a Tree)?

The time complexity for LeetCode 2925 (Maximum Score After Applying Operations on a Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2925 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2925 in Java, C++, or Python.

Back to LeetCode Solutions