2925. Maximum Score After Applying Operations on a Tree


Problem Description

In this problem, we're given an undirected tree consisting of n nodes labeled from 0 to n - 1, where node 0 is the root of the tree. The tree is represented by a 2D integer array of edges, each indicating a connection between two nodes. Along with the structure of the tree, we also have an integer array values that represents a unique value associated with each node.

As a player, you have the opportunity to increase your score, which starts from 0. This can be achieved through a set of operations you can perform on any node in the tree. An operation involves selecting a node i, adding its value to your score, and then setting its value to 0.

The objective is to achieve the maximum score possible. The challenge, however, is to ensure the tree remains "healthy" after you perform any number of operations. A tree is considered healthy if the sum of values from the root to any leaf node is different than zero, which means every path from the root to a leaf must include at least one node with a non-zero value.

The problem asks us to figure out what sequence of operations will yield the highest possible score while keeping the tree healthy.

Intuition

The solution approach involves dynamic programming (DP) on trees, which is a powerful technique used to solve problems that can be broken down into overlapping subproblems on a tree data structure.

The first insight in tackling this problem is acknowledging that it requires a selection strategy: which nodes should be selected to maximize score, while ensuring that each path from the root to a leaf node has at least one unselected, thus non-zero, node. This means for any selected node, at least one of its descendants should not be selected so as to satisfy the "healthy tree" condition.

The dfs (depth-first search) function is the heart of our solution. It uses recursion to explore each subtree, starting from the root. It returns a tuple with two values: the first is the sum of all node values in the subtree, and the second is the maximum score achievable for the subtree while satisfying the "healthy" condition.

The dfs function considers both situations: selecting the current node and not selecting it. If the current node is selected, its value is added to the score, but then we must ensure that one child node (at least) is not selected for each path down the subtree. If the current node is not selected, we can freely choose from the children nodes without restrictions.

The use of these recursive calls and the proper accumulation and comparison of values at each level of the tree results in an efficient algorithm that yields the maximum score while preserving the tree's health.

At the end of the process, we return the maximum score that can be obtained, which is given by dfs(0)[1], calling the dfs function starting at the root of the tree.

Learn more about Tree, Depth-First Search and Dynamic Programming patterns.

Solution Approach

The problem's solution employs a tree dynamic programming approach, which is an adaptation of the classic dynamic programming strategy to a tree data structure. The fundamental algorithm used is a Depth-First Search (DFS), which enables us to traverse the tree and solve the problem recursively.

The key data structure utilized to represent the tree is an adjacency list (g in the code), which is an efficient way to represent a graph or tree and enables easy traversal of connected nodes.

Here is a breakdown of how the implementation works, following the DFS paradigm:

  1. Adjacency List Creation: First, we build an adjacency list g to represent the tree structure from the given list of edges. This step prepares us for the traversal, as we can easily refer to all children (connected nodes) of any node in the tree.

  2. Defining DFS Function dfs(i, fa): The function dfs(i, fa) is defined to take two parameters: i, representing the current node, and fa, representing the parent node of i. If fa is -1, it indicates that the current node is the root. This function returns a tuple (int, int) where the first integer represents the sum of values of all nodes in the subtree rooted at i, and the second integer represents the maximum score for that subtree while maintaining it healthy.

  3. Leaf Node Base Case: For a leaf node (a node with no children), the function directly returns its value as the sum since there are no subtrees to consider, and a maximum score of 0, because the leaf node itself must remain unselected to keep the tree healthy.

  4. Recursive DFS Calls: For non-leaf nodes, the function performs DFS calls on all children nodes (excluding the parent node to avoid backtracking). This accumulates the sum of all node values along with computing the maximum score respecting our "healthy tree" constraint.

  5. Selecting and Not Selecting a Node: Two scenarios are considered in each recursive call - if the current node i is selected, we add its value to the score but take the maximum score of its children without adding their values (since at least one descendant must be unselected). If the current node i is not selected, we can freely add the scores from each child's subtree, hence we take the sum of all children nodes' maximum scores.

  6. Combining Results from Children: The results from each child are then combined appropriately to update the sum and maximum score at each step.

  7. Returning the Result: Finally, the initial call to dfs(0) starts the traversal from the root, and the second value in the returned tuple represents the maximum score for the entire tree.

Throughout the process, the decision to add the current node's value to the score or not at each step is what essentially solves the problem while fulfilling the healthy tree condition. The recursive nature of DFS guarantees that all possible scenarios are explored, and the dynamic programming aspect ensures that we are efficiently combining these scenarios to reach an optimal solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider a small tree with 4 nodes labeled from 0 to 3, where node 0 is the root. Suppose we are given the following edges and values:

  • edges = [[0, 1], [0, 2], [1, 3]] meaning there are edges between node 0 and 1, node 0 and 2, and node 1 and 3.
  • values = [4, 2, 1, 3]

The tree structure based on the edges is as follows:

1    0(4)
2   / \
3 1(2) 2(1)
4  |
5 3(3)

The numbers in parentheses represent the unique values associated with each node.

Let's walk through the dfs algorithm using this example:

  1. Adjacency List Creation: From the edges given, we construct an adjacency list:

    1g = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}
  2. Defining DFS Function: We set up our dfs(i, fa) function to operate on this tree.

  3. Leaf Node Base Case: Node 2 is a leaf node; it would return its own value (1, 0). Node 3 is also a leaf; it would return its own value (3, 0).

  4. Recursive DFS Calls: Starting with the root (node 0), we call dfs(1, 0) and dfs(2, 0) to explore node 1 and 2's subtrees.

    • For node 1, it is not a leaf node. It has one child, node 3. So it will call dfs(3, 1).

      • dfs(3, 1) returns (3, 0), as node 3 is a leaf.
    • The dfs call for node 1 then calculates the sum of values as 2 (its own value) + 3 = 5. It considers two scenarios:

      • If we pick node 1, we cannot pick node 3, so the score is 2.
      • If we do not pick node 1, we can pick node 3, so the score is 3.

      The maximum score from node 1's subtree would be max(2, 3) = 3, and it returns (5, 3).

    • For node 2, dfs(2, 0) returns (1, 0) as previously mentioned.

  5. Selecting and Not Selecting Node 0: Now, back at node 0, we combine the results from its children:

    • If we pick node 0, we can't pick nodes 1 and 2, and the score would be the value of node 0 itself, which is 4.
    • If we don't pick node 0, we add up the maximum scores returned by its children (3 from node 1's subtree, 0 from node 2's subtree), thus the score would be 3 + 0 = 3.
  6. Combining Results from Children: The sum of values for the subtree rooted at node 0 is the value of node 0 (4) plus the sum from its children (5 from node 1's subtree, 1 from node 2's subtree) which is 4 + 5 + 1 = 10. The maximum score for node 0's subtree is max(4, 3) which is 4.

  7. Returning the Result: Calling dfs(0) would give us the tuple (10, 4), where the second value, which is 4, is the maximum score we can achieve while keeping the tree healthy.

Thus, our operations would be to perform an operation on node 0 to achieve the maximum score of 4.

Solution Implementation

1from typing import List, Tuple
2
3class Solution:
4    def maximumScoreAfterOperations(
5        self, edges: List[List[int]], values: List[int]
6    ) -> int:
7        # Depth-first search function to calculate maximum score
8        def dfs(node_index: int, parent_index: int = -1) -> Tuple[int, int]:
9            current_score = best_subtree_score = 0
10            is_leaf = True  # To check if the node is a leaf
11          
12            # Iterate over children of the current node
13            for adjacent_node in graph[node_index]:
14                if adjacent_node != parent_index:
15                    is_leaf = False
16                    score_with_adjacent, score_without_adjacent = dfs(adjacent_node, node_index)
17                    # Scoring when including or excluding adjacent node
18                    current_score += score_with_adjacent
19                    best_subtree_score += score_without_adjacent
20          
21            # If it's a leaf node, it can only take its own value
22            if is_leaf:
23                return values[node_index], 0
24          
25            # Return the maximum scores with and without including the current node
26            return (values[node_index] + current_score,
27                    max(values[node_index] + best_subtree_score, current_score))
28
29        # Initialize the graph representation
30        graph = [[] for _ in values]
31      
32        # Build graph from the given edges
33        for a, b in edges:
34            graph[a].append(b)
35            graph[b].append(a)
36      
37        # Start the DFS from the first node and return the best score without including the first node
38        return dfs(0)[1]
39
40# Below is an example of how to use the Solution class
41# my_solution = Solution()
42# maximum_score = my_solution.maximumScoreAfterOperations(edges, values)
43
1class Solution {
2    private List<Integer>[] graph; // Graph represented as an adjacency list
3    private int[] nodeValues; // Values associated with each node
4
5    // Function to calculate the maximum score after performing operations on the graph
6    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
7        int n = values.length; // Number of nodes in the graph
8        graph = new List[n]; // Initialize the adjacency list
9        nodeValues = values;
10        // Fill the graph with empty lists for adjacent nodes
11        Arrays.setAll(graph, index -> new ArrayList<>());
12        // Build the graph using the given edges
13        for (var edge : edges) {
14            int from = edge[0], to = edge[1];
15            graph[from].add(to);
16            graph[to].add(from);
17        }
18        // Perform DFS and return the maximum score from the root note considering it is not selected
19        return dfs(0, -1)[1];
20    }
21
22    // Helper method for performing a DFS traversal on the graph
23    private long[] dfs(int node, int parent) {
24        long includeNode = 0; // Current node's value if it is included
25        long excludeNode = 0; // Current node's value if it is excluded
26        boolean isLeaf = true; // Check if the current node is a leaf node
27
28        // Iterate over all adjacent nodes
29        for (int adjacent : graph[node]) {
30            if (adjacent != parent) { // If the adjacent node is not the parent
31                isLeaf = false; // Current node is not a leaf
32                var valuesFromChild = dfs(adjacent, node); // Recursively apply DFS to the child node
33                includeNode += valuesFromChild[0]; // If current node is included, sum up the excluded values from children
34                excludeNode += valuesFromChild[1]; // If current node is excluded, sum up the max values from children
35            }
36        }
37
38        if (isLeaf) {
39            // If the node is a leaf node, return its value as included and 0 as excluded
40            return new long[]{nodeValues[node], 0};
41        }
42        // If the node is not a leaf node, return the included value and the max of included/excluded for excluding the current node
43        return new long[]{nodeValues[node] + includeNode, Math.max(nodeValues[node] + excludeNode, includeNode)};
44    }
45}
46
1#include <vector>
2#include <functional>
3
4using std::vector;
5using std::function;
6using std::pair;
7using std::max;
8
9class Solution {
10public:
11    long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {
12        int numNodes = values.size();
13        vector<vector<int>> graph(numNodes);
14
15        // Construct the graph from edge list
16        for (const auto& edge : edges) {
17            int from = edge[0], to = edge[1];
18            graph[from].emplace_back(to);
19            graph[to].emplace_back(from);
20        }
21
22        // Use long long type for handling potentially large sums
23        using ll = long long;
24
25        // Define the dfs function using lambda to search the tree and compute scores
26        function<pair<ll, ll>(int, int)> dfs = [&](int node, int parent) -> pair<ll, ll> {
27            ll scoreWithNode = 0, scoreWithoutNode = 0;
28            bool isLeaf = true;
29
30            // Iterate over all the children/neighbors of the current node
31            for (int neighbor : graph[node]) {
32                if (neighbor != parent) {
33                    auto [scoreWithChild, scoreWithoutChild] = dfs(neighbor, node);
34                    scoreWithNode += scoreWithChild;
35                    scoreWithoutNode += scoreWithoutChild;
36                    isLeaf = false;
37                }
38            }
39
40            if (isLeaf) {
41                // If it's a leaf, return its value and 0
42                return {values[node], 0LL};
43            }
44
45            // Return the maximum score of including this node or excluding it
46            return {values[node] + scoreWithNode, max(values[node] + scoreWithoutNode, scoreWithNode)};
47        };
48
49        // Perform dfs from the root (node 0) assuming the tree is rooted at node 0; no parent (-1)
50        auto [scoreWithRoot, scoreWithoutRoot] = dfs(0, -1);
51
52        // The maximum score is found when not including the root score value since 
53        // operations can be only applied to non-root nodes
54        return scoreWithoutRoot;
55    }
56};
57
1function maximumScoreAfterOperations(graphEdges: number[][], nodeValues: number[]): number {
2    // Initialize an adjacency list to represent the graph.
3    const adjacencyList: number[][] = Array.from({ length: nodeValues.length }, () => []);
4
5    // Populate the adjacency list with edges from the input graphEdges.
6    for (const [node1, node2] of graphEdges) {
7        adjacencyList[node1].push(node2);
8        adjacencyList[node2].push(node1);
9    }
10
11    // Helper function that performs Depth-First Search (DFS) on the graph.
12    // It calculates two values for each node: the max score including the node (includeNodeScore) and the max score excluding the node (excludeNodeScore).
13    const performDfs = (currentNode: number, parentNode: number): [number, number] => {
14        // Base scores for including and excluding the current node.
15        let includeNodeScore = 0;
16        let excludeNodeScore = 0;
17        let isLeafNode = true; // flag to check if the node is a leaf
18
19        // Iterate over neighboring nodes.
20        for (const neighbor of adjacencyList[currentNode]) {
21            // Skip the parent node to prevent cycling back in the graph.
22            if (neighbor !== parentNode) {
23                // Perform DFS on the neighboring node.
24                const [neighborIncludeScore, neighborExcludeScore] = performDfs(neighbor, currentNode);
25                // Add up scores from child nodes including and excluding the current node.
26                includeNodeScore += neighborIncludeScore;
27                excludeNodeScore += neighborExcludeScore;
28                // If neighbor nodes are visited, currentNode is not a leaf.
29                isLeafNode = false;
30            }
31        }
32
33        // If the node is a leaf, return its value as part of the includeNodeScore.
34        if (isLeafNode) {
35            return [nodeValues[currentNode], 0];
36        }
37      
38        // When including the current node, add its value to excludeNodeScore from child nodes.
39        // When excluding the current node, take the max of includeNodeScore and excludeNodeScore from child nodes.
40        return [
41            nodeValues[currentNode] + excludeNodeScore, // Including the current node.
42            Math.max(nodeValues[currentNode] + includeNodeScore, excludeNodeScore) // Excluding the current node.
43        ];
44    };
45
46    // Start DFS from the root node (0) with no parent (-1).
47    // Return the maximum score excluding the root node (since the root can't be paired).
48    return performDfs(0, -1)[1];
49}
50

Time and Space Complexity

The given code performs a Depth-First Search (DFS) on a tree represented by nodes and edges. Each node is visited exactly once during DFS, and for each node, the function iterates over all of its adjacent edges. Since the data structure is a tree, it has n - 1 edges for n nodes, meaning that every edge is considered twice (once from either node it connects). Thus, every node and edge is processed a finite and constant number of times.

Time Complexity:

The time complexity is O(n) since each node (n being total number of nodes) is visited once, and the work done at each node is proportional to the degree of the node, which all sum to 2(n - 1) across the entire tree (each undirected edge is counted twice).

Space Complexity:

The space complexity is also O(n) due to several factors:

  • The recursion stack that could, in the worst case, hold a number of frames equal to the height of the tree, which is O(n) in the case of a skewed tree.
  • The adjacency list g that is used to store the graph, which contains a list for each of the n nodes.

Combining these factors leads to the overall space complexity being linear with respect to the number of nodes in the tree.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄