LeetCode Problem 2920

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Tree, Depth-First Search, Memoization

Solution

LeetCode 2920 - Maximum Points After Collecting Coins From All Nodes

Problem Understanding

We are given a tree with n nodes rooted at node 0. Each node contains a certain number of coins. We must collect coins from every node while respecting the tree hierarchy, meaning a node can only be processed after all of its ancestors have already been processed.

At every node, we must choose exactly one of two operations:

1. Collect the node's current coins and gain currentCoins - k points.
2. Collect the node's current coins and gain floor(currentCoins / 2) points. However, this choice also halves the coin count of every node in the entire subtree rooted at that node.

The key challenge is that choosing the second operation affects future decisions. If we halve a node, then all descendants will permanently see reduced coin values. Since multiple ancestors may choose the halving operation, a node's coin value may be divided by two several times before it is eventually processed.

The goal is to maximize the total points collected across all nodes.

The constraints are particularly important:

• n can be as large as 100000, so any solution that explores all decision combinations directly is impossible.
• coins[i] ≤ 10000.
• Since 10000 < 2^14, repeated halving quickly reduces values to zero.
• The input graph is guaranteed to be a valid tree.

An important observation is that a node's final coin value depends only on how many ancestors selected the second operation. The exact ancestors do not matter, only the total number of halvings applied along the path from the root.

Important edge cases include trees where all coin values are zero, trees where k is very large and makes the first operation unattractive, deep chains where many halvings accumulate, and star-shaped trees where decisions at the root affect every other node.

Approaches

Brute Force

A brute-force solution would recursively process the tree and try both choices at every node.

For each node:

• Choose operation 1.
• Choose operation 2.
• Recompute the resulting coin values for all descendants.
• Continue recursively.

Since every node has two possible decisions, the search space contains roughly 2^n possibilities. Even for a few dozen nodes this becomes infeasible, and for n = 100000 it is completely impossible.

The brute-force approach is correct because it examines every valid sequence of decisions, but its exponential complexity makes it unusable.

Key Insight

The crucial observation is that a node does not need to know which ancestors applied the halving operation.

It only needs to know how many times halving has already occurred on the path from the root.

Suppose a node originally contains coins[u].

If shift halvings have already been applied by ancestors, then the effective value seen at this node is:

coins[u] >> shift

because repeated floor division by two is equivalent to a right bit shift.

Therefore, we can define a dynamic programming state:

dp(node, shift)

which represents the maximum score obtainable from the entire subtree rooted at node, assuming shift halvings have already been applied by ancestors.

At each state we have two choices:

• Use operation 1:

• Gain (value - k)

• Children remain at the same shift

• Use operation 2:

• Gain value // 2

• Children receive shift + 1

Since coin values are at most 10000, after about 14 halvings every value becomes zero. Therefore the number of distinct shift states is very small, roughly 14 to 15.

This transforms the problem into tree DP with memoization.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries every decision combination
Optimal	O(n × log(maxCoin))	O(n × log(maxCoin))	Tree DP with memoization

Algorithm Walkthrough

1. Build an adjacency list representation of the tree.
2. Define a DFS state dfs(node, parent, shift).

This state returns the maximum score obtainable from the subtree rooted at node when shift halvings have already been applied by ancestors. 3. Compute the effective coin value at the current node:

value = coins[node] >> shift

4. Evaluate the first operation.

Gain:

value - k

Since this operation does not affect descendants, recursively solve each child using the same shift. 5. Evaluate the second operation.

Gain:

value >> 1

Since the entire subtree becomes halved once more, recursively solve each child using shift + 1. 6. Add the optimal child contributions for each option. 7. Take the maximum of the two choices. 8. Memoize the result for (node, shift) so that repeated states are computed only once. 9. Start the DFS from:

dfs(0, -1, 0)

10. Return the resulting value.

Why it works

For any node, the only information from the path above that influences future decisions is the number of halvings already applied. Once that number is known, the subtree becomes completely independent of the rest of the tree. Therefore dfs(node, shift) captures all necessary information.

The recurrence examines both valid choices at the current node and combines them with optimal solutions for all child subtrees. By induction on subtree size, every state returns the maximum achievable score, so the root state gives the global optimum.

Python Solution

from typing import List
from functools import lru_cache
import sys

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        sys.setrecursionlimit(300000)

        n = len(coins)

        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        MAX_SHIFT = 15

        @lru_cache(None)
        def dfs(node: int, parent: int, shift: int) -> int:
            value = coins[node] >> shift

            option1 = value - k
            for nei in graph[node]:
                if nei != parent:
                    option1 += dfs(nei, node, shift)

            option2 = value >> 1
            next_shift = min(MAX_SHIFT, shift + 1)

            for nei in graph[node]:
                if nei != parent:
                    option2 += dfs(nei, node, next_shift)

            return max(option1, option2)

        return dfs(0, -1, 0)

The solution first builds the tree as an adjacency list. The recursive function dfs(node, parent, shift) represents the DP state.

The variable value stores the effective coin value after all ancestor halvings have been applied. The first option collects value - k points and keeps the same halving count for descendants. The second option collects value // 2 points and increases the halving count for all descendants.

For every child, the appropriate recursive state is added to the corresponding option. The maximum of the two possibilities is stored in the memoization cache and returned.

Because each (node, shift) state is computed only once, the algorithm remains efficient even for very large trees.

Go Solution

func maximumPoints(edges [][]int, coins []int, k int) int {
	n := len(coins)

	graph := make([][]int, n)
	for _, e := range edges {
		u, v := e[0], e[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	const MAX_SHIFT = 15

	memo := make(map[[3]int]int)

	var dfs func(int, int, int) int
	dfs = func(node, parent, shift int) int {
		key := [3]int{node, parent, shift}
		if val, ok := memo[key]; ok {
			return val
		}

		value := coins[node] >> shift

		option1 := value - k
		for _, nei := range graph[node] {
			if nei != parent {
				option1 += dfs(nei, node, shift)
			}
		}

		nextShift := shift + 1
		if nextShift > MAX_SHIFT {
			nextShift = MAX_SHIFT
		}

		option2 := value >> 1
		for _, nei := range graph[node] {
			if nei != parent {
				option2 += dfs(nei, node, nextShift)
			}
		}

		if option2 > option1 {
			option1 = option2
		}

		memo[key] = option1
		return option1
	}

	return dfs(0, -1, 0)
}

The Go implementation follows exactly the same DP recurrence. Since Go does not provide a built-in memoization decorator, a map keyed by (node, parent, shift) is used. Integer overflow is not a concern because the maximum possible score is well within the range of Go's int type.

Worked Examples

Example 1

edges = [[0,1],[1,2],[2,3]]
coins = [10,10,3,3]
k = 5

Tree:

0
|
1
|
2
|
3

Consider the optimal path.

Node	Shift	Effective Coins	Choice	Points
0	0	10	First	10 - 5 = 5
1	0	10	First	10 - 5 = 5
2	0	3	Second	1
3	1	1	Second	0

Total:

5 + 5 + 1 + 0 = 11

The DP explores both choices at every node and discovers that this sequence yields the maximum score.

Example 2

edges = [[0,1],[0,2]]
coins = [8,4,4]
k = 0

Tree:

    0
   / \
  1   2

At every node:

value - k = value

while

value // 2 < value

Therefore operation 1 is always optimal.

Node	Value	Gain
0	8	8
1	4	4
2	4	4

Total:

8 + 4 + 4 = 16

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × log(maxCoin))	Each node is evaluated for only a small number of shift values
Space	O(n × log(maxCoin))	Memoization table plus recursion stack

Since:

coins[i] ≤ 10000

we have:

log2(10000) < 14

Therefore each node participates in only about 15 DP states. The total number of states is approximately 15n, and every tree edge is processed a constant number of times per state, yielding linear complexity up to a small constant factor.

Test Cases

from typing import List

s = Solution()

assert s.maximumPoints(
    [[0,1],[1,2],[2,3]],
    [10,10,3,3],
    5
) == 11  # example 1

assert s.maximumPoints(
    [[0,1],[0,2]],
    [8,4,4],
    0
) == 16  # example 2

assert s.maximumPoints(
    [[0,1]],
    [0,0],
    5
) == 0  # all zero coins

assert s.maximumPoints(
    [[0,1]],
    [1,1],
    100
) == 0  # huge penalty makes halving preferable

assert s.maximumPoints(
    [[0,1],[1,2]],
    [8,8,8],
    0
) == 24  # always choose first operation

assert s.maximumPoints(
    [[0,1],[0,2],[0,3]],
    [16,8,8,8],
    4
) >= 0  # star-shaped tree

assert s.maximumPoints(
    [[0,1],[1,2],[2,3],[3,4]],
    [10000,10000,10000,10000,10000],
    1
) > 0  # deep chain with large values

assert s.maximumPoints(
    [[0,1]],
    [1,0],
    0
) == 1  # leaf with zero coins

assert s.maximumPoints(
    [[0,1]],
    [2,2],
    1
) == 2  # small values with both choices possible

Test Summary

Test	Why
Example 1	Verifies the official sample answer
Example 2	Verifies the official sample answer
All zero coins	Checks handling of zero values
Huge penalty	Ensures negative first-option values are handled
All positive, k = 0	Confirms first operation dominates
Star-shaped tree	Tests root influence on many descendants
Deep chain	Tests repeated halving propagation
Zero-valued leaf	Ensures leaf handling is correct
Small values	Validates behavior near floor-division boundaries

Edge Cases

Very Large Penalty k

When k is much larger than the available coins, the first operation may produce strongly negative scores. A greedy implementation might incorrectly choose it anyway. The DP explicitly evaluates both options and selects whichever produces the larger total score, including cases where halving yields zero and is therefore preferable.

Repeated Halving Until Coins Become Zero

A node may inherit many halving operations from ancestors. Eventually its effective value becomes zero. An implementation that allows unbounded shift states could waste memory and time. This solution caps the shift dimension because once enough halvings have occurred, further halvings cannot change the value.

Deep Trees

The tree may contain up to 100000 nodes and could be a single chain. Such inputs can easily exceed Python's default recursion depth. The implementation increases the recursion limit to safely support deep DFS traversals.

Nodes With Zero Coins

A node may already contain zero coins before any halving occurs. Both operations then contribute zero or negative values. The recurrence naturally handles this situation because it computes both choices and takes the maximum, ensuring the optimal contribution from that subtree is still selected correctly.