Maximum Points After Collecting Coins From All Nodes - Video Solutions

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.