2920. Maximum Points After Collecting Coins From All Nodes

The problem

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] = [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 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 node_i can be collected in one of the following ways:

Collect all the coins, but you will get coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.
Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all the node_j present in the subtree of node_i, 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.length
2 <= n <= 10⁵
0 <= coins[i] <= 10⁴
edges.length == n - 1
0 <= edges[i][0], edges[i][1] < n
0 <= k <= 10⁴

Approach overview

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

Approach 1: DFS with Subtree Points Calculation

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.

Python

```python
def max_points(edges, coins, k):
    from collections import defaultdict
    import math

    def dfs(node, parent):
        max_points = coins[node] - k
        for child in tree[node]:
            if child != parent:
                with_half = dfs(child, node) + math.floor(coins[node] / 2)
                without_half = dfs(child, node)
                max_points += max(with_half, without_half)
        return max_points

    tree = defaultdict(list)
    for a, b in edges:
        tree[a].append(b)
        tree[b].append(a)

    return dfs(0, -1)

# Example usage
print(max_points([[0, 1], [1, 2], [2, 3]], [10, 10, 3, 3], 5))  # Output: 11
```

Java

```java
import java.util.*;

public class CoinCollection {
    public int maxPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
        for (int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]);
            tree.get(edge[1]).add(edge[0]);
        }
        return dfs(tree, coins, k, 0, -1);
    }

    private int dfs(List<List<Integer>> tree, int[] coins, int k, int node, int parent) {
        int maxPoints = coins[node] - k;
        for (int child : tree.get(node)) {
            if (child != parent) {
                int withHalf = dfs(tree, coins, k, child, node) + (coins[node]) / 2;
                int withoutHalf = dfs(tree, coins, k, child, node);
                maxPoints += Math.max(withHalf, withoutHalf);
            }
        }
        return maxPoints;
    }

    public static void main(String[] args) {
        CoinCollection cc = new CoinCollection();
        int[][] edges = {{0, 1}, {1, 2}, {2, 3}};
        int[] coins = {10, 10, 3, 3};
        int k = 5;
        System.out.println(cc.maxPoints(edges, coins, k));
    }
}
```

C++

```cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int dfs(vector<vector<int>>& tree, vector<int>& coins, int k, int node, int parent) {
    int maxPoints = coins[node] - k;
    for (int child : tree[node]) {
        if (child != parent) {
            int withHalf = dfs(tree, coins, k, child, node) + floor(coins[node] / 2);
            int withoutHalf = dfs(tree, coins, k, child, node);
            maxPoints += max(withHalf, withoutHalf);
        }
    }
    return maxPoints;
}

int maxPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
    int n = coins.size();
    vector<vector<int>> tree(n);
    for (auto& edge : edges) {
        tree[edge[0]].push_back(edge[1]);
        tree[edge[1]].push_back(edge[0]);
    }
    return dfs(tree, coins, k, 0, -1);
}
```

JavaScript

```javascript
function maxPoints(edges, coins, k) {
    const tree = Array.from({ length: coins.length }, () => []);
    for (const [a, b] of edges) {
        tree[a].push(b);
        tree[b].push(a);
    }

    function dfs(node, parent) {
        let maxPoints = coins[node] - k;
        for (const child of tree[node]) {
            if (child !== parent) {
                const withHalf = dfs(child, node) + Math.floor(coins[node] / 2);
                const withoutHalf = dfs(child, node);
                maxPoints += Math.max(withHalf, withoutHalf);
            }
        }
        return maxPoints;
    }

    return dfs(0, -1);
}

// Example usage
console.log(maxPoints([[0, 1], [1, 2], [2, 3]], [10, 10, 3, 3], 5)); // Output: 11
```

```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int maxPoints(struct Edge** edges, int edgesSize, int* coins, int coinsSize, int k) {
    // Your implementation will go here
    // Represent the tree and create a DFS helper
    return -1;
}

int main() {
    // Example test case
    int coins[] = {10, 10, 3, 3};
    int k = 5;
    struct Edge* edges[] = {&Edge(0, 1), &Edge(1, 2), &Edge(2, 3)};
    printf("%d\n", maxPoints(edges, 3, coins, 4, k));
}
```

```csharp
using System;
using System.Collections.Generic;

class Solution {
    public int MaxPoints(int[][] edges, int[] coins, int k) {
        int n = coins.Length;
        List<List<int>> tree = new List<List<int>>();
        for (int i = 0; i < n; i++) tree.Add(new List<int>());
        foreach (var edge in edges) {
            tree[edge[0]].Add(edge[1]);
            tree[edge[1]].Add(edge[0]);
        }
        return DFS(tree, coins, k, 0, -1);
    }

    private int DFS(List<List<int>> tree, int[] coins, int k, int node, int parent) {
        int maxPoints = coins[node] - k;
        foreach (var child in tree[node]) {
            if (child != parent) {
                int withHalf = DFS(tree, coins, k, child, node) + coins[node] / 2;
                int withoutHalf = DFS(tree, coins, k, child, node);
                maxPoints += Math.Max(withHalf, withoutHalf);
            }
        }
        return maxPoints;
    }
}

class Program {
    static void Main(string[] args) {
        var solution = new Solution();
        int[][] edges = new int[][] { new int[] { 0, 1 }, new int[] { 1, 2 }, new int[] { 2, 3 } };
        int[] coins = new int[] { 10, 10, 3, 3 };
        int k = 5;
        Console.WriteLine(solution.MaxPoints(edges, coins, k)); // Output: 11
    }
}
```

The Python function prepares an adjacency list to represent the tree and uses DFS to calculate the largest possible points from the root to all nodes. It recursively evaluates points by either reducing the node's coins by a fixed amount or by halving the subtree.

Complexity

Time Complexity: O(n), since each node is visited once.
Space Complexity: O(n) for tree representation using dictionaries and recursion depth.

Try this approach in the editor

Approach 2: Dynamic Programming on Trees

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.

Python

```python
def max_points(edges, coins, k):
    from collections import defaultdict
    import math

    tree = defaultdict(list)
    for a, b in edges:
        tree[a].append(b)
        tree[b].append(a)

    n = len(coins)
    dp = [-1] * n

    def max_points_dp(node, parent):
        if dp[node] != -1:
            return dp[node]
        max_points = coins[node] - k
        for child in tree[node]:
            if child == parent:
                continue
            with_half = max_points_dp(child, node) + math.floor(coins[node] / 2)
            without_half = max_points_dp(child, node)
            max_points += max(with_half, without_half)
        dp[node] = max_points
        return max_points

    return max_points_dp(0, -1)

# Example usage
print(max_points([[0, 1], [0, 2]], [8, 4, 4], 0))  # Output: 16
```

Java

```java
import java.util.*;

public class CoinCollectionDP {
    public int maxPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
        for (int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]);
            tree.get(edge[1]).add(edge[0]);
        }
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        return maxPointsDP(0, tree, coins, k, dp, -1);
    }

    private int maxPointsDP(int node, List<List<Integer>> tree, int[] coins, int k, int[] dp, int parent) {
        if (dp[node] != -1) return dp[node];
        int maxPoints = coins[node] - k;
        for (int child : tree.get(node)) {
            if (child == parent) continue;
            int withHalf = maxPointsDP(child, tree, coins, k, dp, node) + coins[node] / 2;
            int withoutHalf = maxPointsDP(child, tree, coins, k, dp, node);
            maxPoints += Math.max(withHalf, withoutHalf);
        }
        return dp[node] = maxPoints;
    }

    public static void main(String[] args) {
        CoinCollectionDP ccDP = new CoinCollectionDP();
        int[][] edges = {{0, 1}, {0, 2}};
        int[] coins = {8, 4, 4};
        int k = 0;
        System.out.println(ccDP.maxPoints(edges, coins, k));
    }
}
```

C++

```cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int maxPointsDP(int node, vector<vector<int>>& tree, vector<int>& coins, int k, vector<int>& dp, int parent) {
    if (dp[node] != -1) return dp[node];
    int maxPoints = coins[node] - k;
    for (int child : tree[node]) {
        if (child == parent) continue;
        int withHalf = maxPointsDP(child, tree, coins, k, dp, node) + floor(coins[node] / 2);
        int withoutHalf = maxPointsDP(child, tree, coins, k, dp, node);
        maxPoints += max(withHalf, withoutHalf);
    }
    return dp[node] = maxPoints;
}

int maxPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
    int n = coins.size();
    vector<vector<int>> tree(n);
    for (auto& edge : edges) {
        tree[edge[0]].push_back(edge[1]);
        tree[edge[1]].push_back(edge[0]);
    }
    vector<int> dp(n, -1);
    return maxPointsDP(0, tree, coins, k, dp, -1);
}
```

JavaScript

```javascript
function maxPoints(edges, coins, k) {
    const tree = Array.from({ length: coins.length }, () => []);
    for (const [a, b] of edges) {
        tree[a].push(b);
        tree[b].push(a);
    }

    const dp = Array(coins.length).fill(-1);

    function maxPointsDP(node, parent) {
        if (dp[node] !== -1) {
            return dp[node];
        }
        let maxPoints = coins[node] - k;
        for (const child of tree[node]) {
            if (child === parent) continue;

            const withHalf = maxPointsDP(child, node) + Math.floor(coins[node] / 2);
            const withoutHalf = maxPointsDP(child, node);

            maxPoints += Math.max(withHalf, withoutHalf);
        }
        return dp[node] = maxPoints;
    }

    return maxPointsDP(0, -1);
}

// Example usage
console.log(maxPoints([[0, 1], [0, 2]], [8, 4, 4], 0)); // Output: 16
```

```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int maxPoints(int** edges, int edgesSize, int* coins, int coinsSize, int k) {
    // Dynamic Programming Table Initialization
    // Implement dynamic programming logic
    return -1;
}

int main() {
    // Example test case
    int coins[] = {8, 4, 4};
    int k = 0;
    int* edges[] = { (int[]) {0, 1}, (int[]) {0, 2} };
    printf("%d\n", maxPoints(edges, 2, coins, 3, k));
}
```

```csharp
using System;
using System.Collections.Generic;

class Solution {
    public int MaxPoints(int[][] edges, int[] coins, int k) {
        int n = coins.Length;
        List<List<int>> tree = new List<List<int>>();
        for (int i = 0; i < n; i++) tree.Add(new List<int>());
        foreach (var edge in edges) {
            tree[edge[0]].Add(edge[1]);
            tree[edge[1]].Add(edge[0]);
        }
        int[] dp = new int[n];
        Array.Fill(dp, -1);
        return MaxPointsDP(0, tree, coins, k, dp, -1);
    }

    private int MaxPointsDP(int node, List<List<int>> tree, int[] coins, int k, int[] dp, int parent) {
        if (dp[node] != -1) return dp[node];
        int maxPoints = coins[node] - k;
        foreach (var child in tree[node]) {
            if (child == parent) continue;
            int withHalf = MaxPointsDP(child, tree, coins, k, dp, node) + coins[node] / 2;
            int withoutHalf = MaxPointsDP(child, tree, coins, k, dp, node);
            maxPoints += Math.Max(withHalf, withoutHalf);
        }
        dp[node] = maxPoints;
        return maxPoints;
    }
}

class Program {
    static void Main(string[] args) {
        var solution = new Solution();
        int[][] edges = new int[][] { new int[] { 0, 1 }, new int[] { 0, 2 } };
        int[] coins = new int[] { 8, 4, 4 };
        int k = 0;
        Console.WriteLine(solution.MaxPoints(edges, coins, k)); // Output: 16
    }
}
```

This Python implementation executes maximum point collection through dynamic programming, exploring node dependencies and choices. It leverages call memoization (dp) to fix and reuse previously calculated results.

Complexity

Time Complexity: O(n), from dp transitions following single path calculations.
Space Complexity: O(n), utilizing list structures for graph and dp arrays.

Try this approach in the editor

Approach 3: Memoization Search

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

TypeScript

function maximumPoints(edges: number[][], coins: number[], k: number): number {
    const n = coins.length;
    const f: number[][] = Array.from({ length: n }, () => Array(15).fill(-1));
    const g: number[][] = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        g[a].push(b);
        g[b].push(a);
    }
    const dfs = (i: number, fa: number, j: number): number => {
        if (f[i][j] !== -1) {
            return f[i][j];
        }
        let a = (coins[i] >> j) - k;
        let b = coins[i] >> (j + 1);
        for (const c of g[i]) {
            if (c !== fa) {
                a += dfs(c, i, j);
                if (j < 14) {
                    b += dfs(c, i, j + 1);
                }
            }
        }
        return (f[i][j] = Math.max(a, b));
    };
    return dfs(0, -1, 0);
}

func maximumPoints(edges [][]int, coins []int, k int) int {
	n := len(coins)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, 15)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	var dfs func(int, int, int) int
	dfs = func(i, fa, j int) int {
		if f[i][j] != -1 {
			return f[i][j]
		}
		a := (coins[i] >> j) - k
		b := coins[i] >> (j + 1)
		for _, c := range g[i] {
			if c != fa {
				a += dfs(c, i, j)
				if j < 14 {
					b += dfs(c, i, j+1)
				}
			}
		}
		f[i][j] = max(a, b)
		return f[i][j]
	}
	return dfs(0, -1, 0)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
DFS with Subtree Points Calculation	Time Complexity: O(n), since each node is visited once. Space Complexity: O(n) for tree representation using dictionaries and recursion depth.
Dynamic Programming on Trees	Time Complexity: O(n), from dp transitions following single path calculations. Space Complexity: O(n), utilizing list structures for graph and dp arrays.
Memoization Search	–

Complexity analysis

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

Frequently asked questions

Is Maximum Points After Collecting Coins From All Nodes easy or hard?

Maximum Points After Collecting Coins From All Nodes is classified as a Hard problem. It combines multiple advanced concepts including tree traversal, dynamic programming states, and bit manipulation, which makes the reasoning more complex than standard DFS problems.

Maximum Points After Collecting Coins From All Nodes Python/Java solution

Python, Java, and C++ implementations typically use DFS with memoization. A function dfs(node, parent, shift) computes the best score from that subtree. Results are cached in a DP structure to avoid recomputation, giving O(n * k) performance.

How to solve Maximum Points After Collecting Coins From All Nodes in O(n)?

A strict O(n) solution is not typical because each node must be evaluated across multiple reduction states. However, since the number of halving operations is bounded by about log2(maxCoin), the effective complexity becomes O(n * k) with k ≈ 14, which behaves close to linear in practice.

What is the best approach for Maximum Points After Collecting Coins From All Nodes?

The most effective approach is tree dynamic programming with memoized DFS. Each state is defined by (node, number of coin halvings applied so far). For every node you evaluate two choices: collect coins with penalty k or halve the value for the subtree. Memoizing results keeps the complexity around O(n * k), where k is the maximum number of reductions (about 14).

Is Maximum Points After Collecting Coins From All Nodes asked at Google/Amazon/Meta?

Tree dynamic programming problems similar to this frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving subtree decisions, state propagation during DFS, and maximizing scores on trees are common interview patterns.

What data structure is used in Maximum Points After Collecting Coins From All Nodes?

The problem primarily uses a tree represented with an adjacency list. The algorithm combines Depth-First Search traversal with dynamic programming states and bit manipulation (right shift) to simulate repeated coin halving efficiently.

What is the time complexity of Maximum Points After Collecting Coins From All Nodes?

The optimal solutions run in O(n * k) time, where n is the number of nodes in the tree and k is the number of possible coin reductions. Since each halving quickly reduces the value, k is small (roughly log of the maximum coin value). Space complexity is also O(n * k) due to memoization or DP storage.

Maximum Points After Collecting Coins From All Nodes solution and explanation

The problem

Approach overview

Approach 1: DFS with Subtree Points Calculation

Approach 2: Dynamic Programming on Trees

Approach 3: Memoization Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Points After Collecting Coins From All Nodes solution and explanation

The problem

Approach overview

Approach 1: DFS with Subtree Points Calculation

Approach 2: Dynamic Programming on Trees

Approach 3: Memoization Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems