There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1. 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 array coins of size n where coins[i] indicates the number of coins in the vertex i, and an integer k.
Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.
Coins at nodei can be collected in one of the following ways:
coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.floor(coins[i] / 2) points. If this way is used, then for all the nodej present in the subtree of nodei, coins[j] will get reduced to floor(coins[j] / 2).Return the maximum points you can get after collecting the coins from all the tree nodes.
Example 1:
Input: edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5 Output: 11 Explanation: Collect all the coins from node 0 using the first way. Total points = 10 - 5 = 5. Collect all the coins from node 1 using the first way. Total points = 5 + (10 - 5) = 10. Collect all the coins from node 2 using the second way so coins left at node 3 will be floor(3 / 2) = 1. Total points = 10 + floor(3 / 2) = 11. Collect all the coins from node 3 using the second way. Total points = 11 + floor(1 / 2) = 11. It can be shown that the maximum points we can get after collecting coins from all the nodes is 11.
Example 2:
Input: edges = [[0,1],[0,2]], coins = [8,4,4], k = 0 Output: 16 Explanation: Coins will be collected from all the nodes using the first way. Therefore, total points = (8 - 0) + (4 - 0) + (4 - 0) = 16.
Constraints:
n == coins.length2 <= n <= 1050 <= coins[i] <= 104edges.length == n - 10 <= edges[i][0], edges[i][1] < n0 <= k <= 104Problem Overview: You are given a tree where each node contains some coins. Starting from the root, you collect coins while traversing the tree, but each node forces a choice: take the coins now with a penalty k, or halve the coin value for the current node and all nodes in its subtree. The goal is to maximize the total points collected after visiting every node.
This structure immediately points to tree traversal combined with state tracking. Each decision affects the entire subtree, so the algorithm must remember how many times the coin value has been halved along the path from the root.
Approach 1: DFS with Subtree Points Calculation (O(n * k) time, O(n * k) space)
Traverse the tree using Depth-First Search. The key state is (node, shift), where shift represents how many times the coin values have been halved so far. For each node, compute two options: collect the current coin value after applying shift reductions and subtract k, or apply another reduction using a bit shift (coins[node] >> (shift + 1)) and propagate the increased reduction level to children. Recursively evaluate both choices for each child and accumulate the best result. Memoization avoids recomputing states because the same node and reduction level can appear through different paths. The number of reduction states is small (about 14 since coin values shrink quickly), which keeps the DFS efficient.
This approach works well because the tree has no cycles and each decision only affects the subtree. Bit shifting efficiently models repeated halving, making the calculation constant time per state.
Approach 2: Dynamic Programming on Trees (O(n * k) time, O(n * k) space)
This version explicitly models the problem as Dynamic Programming on a tree. Define dp[node][shift] as the maximum points obtainable from the subtree rooted at node when the coin value has been halved shift times. During DFS, compute results for children first, then evaluate the two choices at the current node: take coins now or apply another halving. For the "take" option, add (coins[node] >> shift) - k plus the best values from children with the same shift. For the "halve" option, use (coins[node] >> (shift + 1)) and combine with children evaluated at shift + 1. Store the maximum in the DP table.
This formulation makes the transition logic explicit and easier to reason about in interviews. The DP table ensures each (node, shift) state is computed once, giving linear complexity relative to the number of nodes multiplied by the limited number of reduction states.
Recommended for interviews: Tree DP with memoized DFS. Interviewers expect you to recognize that subtree decisions require passing state down the recursion. Starting with the DFS state definition shows understanding of tree traversal, while optimizing with memoization demonstrates strong dynamic programming skills.
This approach leverages Depth-First Search (DFS) to traverse the tree and calculate the maximum possible points from collecting coins. We perform a DFS starting from the root node (0) and for each node, decide whether to collect its coins using the first or second method. The first method subtracts k from the node's coin value, whereas the second reduces all subtree nodes' coins by half. The key is to recursively calculate and choose the best option for every node.
The C solution involves organizing the graph structure using adjacency lists. The DFS function explores each node, calculating potential points for both ways of collecting coins (subtracting k or halving the subtree's coins). By comparing results, it ensures the maximum points are achieved.
Time Complexity: O(n) since we visit each node once.
Space Complexity: O(n) to store adjacency list and recursion stack.
This approach uses dynamic programming to solve the problem on trees, known as DP on trees. We maintain a dp array to store the maximum points that can be collected from each subtree starting from a node. The transition relations help in deciding whether a node should be included without penalties or adjusted by halving the subtree values.
The C code outlines the skeleton where DP on trees is applied to compute potential points efficiently. By transforming each edge into transitions in the dp table, it evaluates maximal paths recursively and optimizes score calculation.
Time Complexity: O(n), typical for tree dynamic programming where each node contributes.
Space Complexity: O(n) for storing intermediate dp results.
First, we construct a graph g based on the edges given in the problem, where g[i] represents all adjacent nodes of node i. Then we can use the method of memoization search to solve this problem.
We design a function dfs(i, fa, j), which represents that the current node is i, the parent node is fa, the number of gold coins of the current node needs to be shifted to the right by j bits, and the maximum score that can be obtained.
The execution process of the function dfs(i, fa, j) is as follows:
If we use the first method to collect the gold coins of the current node, then the score of the current node is (coins[i] >> j) - k. Then we traverse all the adjacent nodes c of the current node. If c is not equal to fa, then we add the result of dfs(c, i, j) to the score of the current node.
If we use the second method to collect the gold coins of the current node, then the score of the current node is coins[i] >> (j + 1). Then we traverse all the adjacent nodes c of the current node. If c is not equal to fa, then we add the result of dfs(c, i, j + 1) to the score of the current node. Note that since the maximum value of coins[i] given in the problem is 10^4, we can only shift to the right by at most 14 bits, so that the value of coins[i] >> (j + 1) is 0.
Finally, we return the maximum score that can be obtained by using the two methods at the current node.
In order to avoid repeated calculations, we use the method of memoization search and store the result of dfs(i, fa, j) in f[i][j], where f[i][j] represents that the current node is i, the parent node is fa, the number of gold coins of the current node needs to be shifted to the right by j bits, and the maximum score that can be obtained.
The time complexity is O(n times log M), and the space complexity is O(n times log M). Where M represents the maximum value of coins[i].
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DFS with Subtree Points Calculation | Time Complexity: O(n) since we visit each node once. |
| Dynamic Programming on Trees | Time Complexity: O(n), typical for tree dynamic programming where each node contributes. |
| Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Subtree Points Calculation | O(n * k) | O(n * k) | General solution using recursion and memoization; easiest to implement |
| Dynamic Programming on Trees | O(n * k) | O(n * k) | Best for interviews when you want a clear DP state definition |
Maximum Points After Collecting Coins From All Nodes | Memoization | Optimisations | Leetcode - 2920 • codestorywithMIK • 3,932 views views
Watch 8 more video solutions →Practice Maximum Points After Collecting Coins From All Nodes with our built-in code editor and test cases.
Practice on FleetCode