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] = [ai, bi] indicates that there is an edge between nodes ai and bi 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 nodei 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 nodej present in the subtree of nodei, coins[j] will get reduced to floor(coins[j] / 2).

Return themaximum points you can get after collecting the coins from all the tree nodes.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


![](https://assets.leetcode.com/uploads/2023/09/18/ex1-copy.png)

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

1
2
3
4
5
6
7


**![](https://assets.leetcode.com/uploads/2023/09/18/ex2.png)**

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^5
  • 0 <= coins[i] <= 10^4
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 0 <= k <= 10^4

Solution

Method 1 – Dynamic Programming on Trees (DFS with State)

Intuition

At each node, we have two choices: collect coins with penalty (coins[i] - k) or collect coins with halving (and halve all coins in the subtree). We use DFS to compute, for each node, the maximum points for both choices, propagating the effect of halving down the tree. We use memoization to avoid recomputation.

Approach

  1. Build the tree as an adjacency list.
  2. Define a DFS function that returns the maximum points for a subtree rooted at u, with a flag indicating if the coins are halved.
  3. For each node, try both options:
    • Option 1: Collect with penalty, sum the best results from children (not halved).
    • Option 2: Collect with halving, sum the best results from children (halved), and halve the coins for this node and all descendants.
  4. Use memoization to cache results for each node and halved state.
  5. Return the maximum of both options at the root.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int dfs(int u, int p, bool halved, vector<vector<int>>& g, vector<int>& coins, int k, map<pair<int,bool>, int>& memo) {
        auto key = make_pair(u, halved);
        if (memo.count(key)) return memo[key];
        int c = halved ? coins[u] / 2 : coins[u];
        // Option 1: collect with penalty
        int opt1 = c - k;
        for (int v : g[u]) if (v != p) opt1 += dfs(v, u, false, g, coins, k, memo);
        // Option 2: collect with halving
        int opt2 = c / 2;
        for (int v : g[u]) if (v != p) opt2 += dfs(v, u, true, g, coins, k, memo);
        return memo[key] = max(opt1, opt2);
    }
    int maximumPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
        int n = coins.size();
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        map<pair<int,bool>, int> memo;
        return dfs(0, -1, false, g, coins, k, memo);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func maximumPoints(edges [][]int, coins []int, k int) int {
    n := len(coins)
    g := make([][]int, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        g[e[1]] = append(g[e[1]], e[0])
    }
    memo := map[[2]int]int{}
    var dfs func(u, p, halved int) int
    dfs = func(u, p, halved int) int {
        key := [2]int{u, halved}
        if v, ok := memo[key]; ok {
            return v
        }
        c := coins[u]
        if halved == 1 {
            c /= 2
        }
        opt1 := c - k
        for _, v := range g[u] {
            if v != p {
                opt1 += dfs(v, u, 0)
            }
        }
        opt2 := c / 2
        for _, v := range g[u] {
            if v != p {
                opt2 += dfs(v, u, 1)
            }
        }
        res := opt1
        if opt2 > res {
            res = opt2
        }
        memo[key] = res
        return res
    }
    return dfs(0, -1, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    Map<String, Integer> memo = new HashMap<>();
    public int maximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        return dfs(0, -1, false, g, coins, k);
    }
    int dfs(int u, int p, boolean halved, List<Integer>[] g, int[] coins, int k) {
        String key = u + "," + halved;
        if (memo.containsKey(key)) return memo.get(key);
        int c = halved ? coins[u] / 2 : coins[u];
        int opt1 = c - k;
        for (int v : g[u]) if (v != p) opt1 += dfs(v, u, false, g, coins, k);
        int opt2 = c / 2;
        for (int v : g[u]) if (v != p) opt2 += dfs(v, u, true, g, coins, k);
        int res = Math.max(opt1, opt2);
        memo.put(key, res);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    val memo = mutableMapOf<Pair<Int, Boolean>, Int>()
    fun maximumPoints(edges: Array<IntArray>, coins: IntArray, k: Int): Int {
        val n = coins.size
        val g = Array(n) { mutableListOf<Int>() }
        for (e in edges) {
            g[e[0]].add(e[1])
            g[e[1]].add(e[0])
        }
        fun dfs(u: Int, p: Int, halved: Boolean): Int {
            val key = u to halved
            memo[key]?.let { return it }
            val c = if (halved) coins[u] / 2 else coins[u]
            var opt1 = c - k
            for (v in g[u]) if (v != p) opt1 += dfs(v, u, false)
            var opt2 = c / 2
            for (v in g[u]) if (v != p) opt2 += dfs(v, u, true)
            val res = maxOf(opt1, opt2)
            memo[key] = res
            return res
        }
        return dfs(0, -1, false)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def maximumPoints(self, edges: list[list[int]], coins: list[int], k: int) -> int:
        from functools import lru_cache
        n = len(coins)
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        from sys import setrecursionlimit
        setrecursionlimit(1 << 20)
        @lru_cache(None)
        def dfs(u: int, p: int, halved: bool) -> int:
            c = coins[u] // 2 if halved else coins[u]
            opt1 = c - k + sum(dfs(v, u, False) for v in g[u] if v != p)
            opt2 = c // 2 + sum(dfs(v, u, True) for v in g[u] if v != p)
            return max(opt1, opt2)
        return dfs(0, -1, False)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn maximum_points(edges: Vec<Vec<i32>>, coins: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        fn dfs(u: usize, p: i32, halved: bool, g: &Vec<Vec<usize>>, coins: &Vec<i32>, k: i32, memo: &mut HashMap<(usize, i32, bool), i32>) -> i32 {
            if let Some(&v) = memo.get(&(u, p, halved)) { return v; }
            let c = if halved { coins[u] / 2 } else { coins[u] };
            let mut opt1 = c - k;
            for &v in &g[u] {
                if v as i32 != p {
                    opt1 += dfs(v, u as i32, false, g, coins, k, memo);
                }
            }
            let mut opt2 = c / 2;
            for &v in &g[u] {
                if v as i32 != p {
                    opt2 += dfs(v, u as i32, true, g, coins, k, memo);
                }
            }
            let res = opt1.max(opt2);
            memo.insert((u, p, halved), res);
            res
        }
        let n = coins.len();
        let mut g = vec![vec![]; n];
        for e in &edges {
            g[e[0] as usize].push(e[1] as usize);
            g[e[1] as usize].push(e[0] as usize);
        }
        let mut memo = HashMap::new();
        dfs(0, -1, false, &g, &coins, k, &mut memo)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    maximumPoints(edges: number[][], coins: number[], k: number): number {
        const n = coins.length;
        const g: number[][] = Array.from({length: n}, () => []);
        for (const [a, b] of edges) {
            g[a].push(b);
            g[b].push(a);
        }
        const memo = new Map<string, number>();
        function dfs(u: number, p: number, halved: boolean): number {
            const key = `${u},${p},${halved}`;
            if (memo.has(key)) return memo.get(key)!;
            const c = halved ? Math.floor(coins[u] / 2) : coins[u];
            let opt1 = c - k;
            for (const v of g[u]) if (v !== p) opt1 += dfs(v, u, false);
            let opt2 = Math.floor(c / 2);
            for (const v of g[u]) if (v !== p) opt2 += dfs(v, u, true);
            const res = Math.max(opt1, opt2);
            memo.set(key, res);
            return res;
        }
        return dfs(0, -1, false);
    }
}

Complexity

  • ⏰ Time complexity: O(n * 2) — Each node and state is visited at most twice (halved or not).
  • 🧺 Space complexity: O(n) — For the recursion stack and memoization.