Maximum points after collecting coins from all nodes

Array Dynamic Programming Bit Manipulation Tree Depth-First Search Memoization

36.3% acceptance

Feb 25, 2026

237

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, and a 0-indexed array coins of size n, 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: 1. Collect all the coins, but you will get coins[i] - k points. 2. Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_points(edges: Vec<Vec<i32>>, coins: Vec<i32>, k: i32) -> i32 {
    let n = coins.len();
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u].push(v);
      adj[v].push(u);
    }

    // dp[node][t] = max points from subtree of node when t halvings have been applied
    // coins[node] effective = coins[node] >> t
    // Since coins[i] <= 10^4 < 2^14, t only matters up to 14
    const MAX_T: usize = 14;
    let mut memo = vec![vec![i32::MIN; MAX_T]; n];

    fn dfs(
      node: usize,
      parent: usize,
      t: usize,
      adj: &Vec<Vec<usize>>,
      coins: &Vec<i32>,
      k: i32,
      memo: &mut Vec<Vec<i32>>,
    ) -> i32 {
      if t >= 14 { return 0; }
      if memo[node][t] != i32::MIN { return memo[node][t]; }

      let c = coins[node] >> t;

      // Option 1: take c - k
      let mut opt1 = c - k;
      for &child in &adj[node] {
        if child != parent {
          opt1 += dfs(child, node, t, adj, coins, k, memo);
        }
      }

      // Option 2: take floor(c / 2), halve all descendants
      let mut opt2 = c >> 1;
      for &child in &adj[node] {
        if child != parent {
          opt2 += dfs(child, node, t + 1, adj, coins, k, memo);
        }
      }

      let res = opt1.max(opt2);
      memo[node][t] = res;
      res
    }

    dfs(0, usize::MAX, 0, &adj, &coins, k, &mut memo)
  }
}