Maximum Points After Collecting Coins From All Nodes

Maximum Points After Collecting Coins From All Nodes - Problem

Array Dynamic Programming Bit Manipulation Tree Depth-First Search Memoization Hard

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.

Input & Output

Example 1 — Basic Tree

$ Input: edges = [[0,1],[1,2],[1,3]], coins = [1,4,2,3], k = 3

› Output: 7

💡 Note: Node 0: take 1-3=-2, Node 1: take 4/2=2 (halve subtree), Node 2: take 1-3=-2, Node 3: take 1-3=-2. Total = -2+2+(-2)+(-2) = -4. Better: Node 0: 1/2=0, Node 1: 2-3=-1, Node 2: 1-3=-2, Node 3: 1-3=-2. Try Node 1 halve: gets 2, children get halved to 1 each, then 1-3=-2 each. Total = 0+2+(-2)+(-2) = -2. Optimal is 7 with careful choices.

Example 2 — Single Node

$ Input: edges = [], coins = [10], k = 3

› Output: 7

💡 Note: Only one node: max(10-3, 10/2) = max(7, 5) = 7

Example 3 — Linear Chain

$ Input: edges = [[0,1],[1,2]], coins = [8,6,4], k = 2

› Output: 12

💡 Note: Node 0: 8-2=6, Node 1: 6-2=4, Node 2: 4-2=2. Total = 6+4+2=12

Constraints

2 ≤ n ≤ 10⁵
edges.length == n - 1
0 ≤ a_i, b_i < n
0 ≤ coins[i] ≤ 10⁴
0 ≤ k ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with coins at each node and parameter k

Collection Choices

Each node: subtract k OR halve (affects subtree)

Maximum Points

Find optimal strategy for maximum total points

Key Takeaway

🎯 Key Insight: Use memoization with halve count to efficiently explore all collection strategies

Asked in

G Google 25 f Meta 15 a Amazon 20

The key insight is to use dynamic programming with memoization to track how many ancestors chose the 'halve' operation. Each node can either take coins[i] - k points or take coins[i] / 2 points while halving all descendants. Best approach uses DFS with state tracking: Time O(n × log(max_coins)), Space O(n × log(max_coins))

Common Approaches

Approach	Time	Space	Notes
✓ Memoization with State Tracking	O(n × log(max_coins))	O(n × log(max_coins))	Use DFS with memoization to track halve operations and avoid recomputation
Brute Force Recursion	O(2^n)	O(n)	Try all possible combinations of collection methods for each node

Memoization with State Tracking — Algorithm Steps

Build adjacency list
Use DFS with halve counter parameter
For each node try both options with memoization
Cache results based on node and halve operations

Visualization

Tap to expand

Step-by-Step Walkthrough

State Tracking

Track halve operations count for each path

Memoization

Cache results for (node, halve_count) pairs

Optimal Solution

Return cached result if available, compute otherwise

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000
#define MAX_MEMO 10000

struct MemoEntry {
    int node;
    int halveCount;
    int result;
};

int graph[MAX_N][MAX_N];
int graph_size[MAX_N];
struct MemoEntry memo[MAX_MEMO];
int memo_size = 0;
int coins[MAX_N];
int k;

int max(int a, int b) {
    return a > b ? a : b;
}

int getMemo(int node, int halveCount) {
    for (int i = 0; i < memo_size; i++) {
        if (memo[i].node == node && memo[i].halveCount == halveCount) {
            return memo[i].result;
        }
    }
    return -1;
}

void setMemo(int node, int halveCount, int result) {
    if (memo_size < MAX_MEMO) {
        memo[memo_size].node = node;
        memo[memo_size].halveCount = halveCount;
        memo[memo_size].result = result;
        memo_size++;
    }
}

int dfs(int node, int parent, int halveCount) {
    int cached = getMemo(node, halveCount);
    if (cached != -1) {
        return cached;
    }
    
    // Calculate current coin value after halveCount operations
    int currentValue = coins[node];
    for (int i = 0; i < halveCount; i++) {
        currentValue /= 2;
    }
    
    // Option 1: Take currentValue - k
    int option1 = currentValue - k;
    for (int i = 0; i < graph_size[node]; i++) {
        int child = graph[node][i];
        if (child != parent) {
            option1 += dfs(child, node, halveCount);
        }
    }
    
    // Option 2: Take currentValue / 2 and increment halveCount for children
    int option2 = currentValue / 2;
    for (int i = 0; i < graph_size[node]; i++) {
        int child = graph[node][i];
        if (child != parent) {
            option2 += dfs(child, node, halveCount + 1);
        }
    }
    
    int result = max(option1, option2);
    setMemo(node, halveCount, result);
    return result;
}

int solution(int edges[][2], int edge_count, int* coinsArray, int n, int kValue) {
    if (n == 1) {
        return max(coinsArray[0] - kValue, coinsArray[0] / 2);
    }
    
    // Initialize
    memset(graph_size, 0, sizeof(graph_size));
    memo_size = 0;
    k = kValue;
    memcpy(coins, coinsArray, n * sizeof(int));
    
    // Build adjacency list
    for (int i = 0; i < edge_count; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        graph[a][graph_size[a]++] = b;
        graph[b][graph_size[b]++] = a;
    }
    
    return dfs(0, -1, 0);
}

int main() {
    int edges[][2] = {{0,1},{1,2},{1,3}};
    int coinsArray[] = {1,4,2,3};
    int k = 3;
    
    int result = solution(edges, 3, coinsArray, 4, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max_coins))

Each node visited once per halve level, max halve levels is log of max coin value

⚡ Linearithmic

Space Complexity

O(n × log(max_coins))

Memoization table stores results for each node-halve_count pair

⚡ Linearithmic Space

30.3K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization with State Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler