3562. Maximum Profit from Trading Stocks with Discounts

HardTreeDepth-First SearchArrayDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n, representing the number of employees in a company. Each employee has a unique ID from 1 to n, where employee 1 is the CEO and is the direct or indirect boss of every other employee.

You are given two 1-based integer arrays, present and future, each of length n, where:

present[i] is the current price at which the ith employee can buy a stock today.
future[i] is the expected price at which the ith employee can sell the stock tomorrow.

The company's hierarchy is described by a 2D integer array hierarchy, where hierarchy[i] = [u_i, v_i] means employee u_i is the direct boss of employee v_i. This structure forms a tree rooted at employee 1.

You also have an integer budget, representing the total funds available for investment.

The company has a discount policy: if an employee's direct boss buys their own stock, then that employee can buy their stock at half the original price, i.e. floor(present[v] / 2).

Your task is to return the maximum profit that can be achieved without exceeding the given budget.

Notes:

You may buy each stock at most once.
You cannot use any profit earned from future stock prices to fund additional investments; all purchases must come only from budget.

The profit gained from buying a stock at cost cost and selling it later is future[v] - cost, where cost is either present[v] (no discount) or floor(present[v] / 2) (if the direct boss bought their own stock). The goal is to choose which employees buy stocks so that the total spent stays within budget and the total profit is maximized.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why DFS?

This problem maps to DFS through a short path in the full flowchart.

The problem is a tree DP with knapsack merging over children, where each node's buy/skip decision and discount state propagate through the tree.

Open in Flowchart

Show step-by-step reasoning

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: The employees and their boss-subordinate relationships form a graph. Each hierarchy[i] = [u_i, v_i] defines an edge between a boss and a subordinate.

Is it a tree?

Yes: Employee 1 (the CEO) is the direct or indirect boss of everyone, and each employee has exactly one direct boss. This structure forms a tree rooted at employee 1, with no cycles.

DFS

Yes: Since the structure is a tree, we use Depth-First Search to traverse it. We recurse from the root down to the leaves, and as each subtree's results return, we combine them into the parent's state using a knapsack-style merge over the budget.

Conclusion: The flowchart guides us to a Depth-First Search pattern. We perform tree DFS from the CEO, computing for each node a profit array indexed by remaining budget and whether the boss bought their stock, then merge child results back up to the root to find the maximum profit within the budget.

Intuition

The first thing to notice is the structure of the problem. Every employee has exactly one direct boss, and employee 1 is the boss of everyone. This means the hierarchy forms a tree rooted at employee 1. Whenever we deal with a tree where each node's answer depends on its children, a natural idea is to solve it from the bottom up using tree DFS.

The second key observation is the discount rule: an employee's buying cost depends on whether their direct boss bought their own stock. The cost is present[v] normally, but drops to floor(present[v] / 2) if the boss bought. This tells us that when we process a node, its decision is influenced by what its parent decided. So for each node we should track two scenarios: one where the boss bought (so this node gets the discount) and one where the boss did not (full price). We capture this with an extra dimension pre, where pre = 1 means the boss bought and pre = 0 means the boss did not.

The third observation is the budget constraint. We have a limited amount of money, each stock can be bought at most once, and we want to maximize total profit. This is exactly the flavor of a 0/1 knapsack problem: each employee is an "item" that either gets bought (paying its cost, gaining future[v] - cost profit) or skipped. The twist is that the items are arranged in a tree, and the cost of children depends on whether the parent was bought.

Putting these ideas together, for each node u we define f[j][pre] as the maximum profit obtainable in the subtree rooted at u when:

the available budget is at most j, and
the parent's purchase state is pre.

To compute this, we first need to combine all of u's children. Since the budget is shared among the children, we merge them one by one using a knapsack: for each child, we decide how much budget j_v to give it. The merge formula is

nxt[j][pre] = max(nxt[j][pre], nxt[j - j_v][pre] + fv[j_v][pre])

This builds up nxt, the best profit obtainable from u's children for every budget level and every parent state.

Finally, we decide whether u itself buys. Its cost is cost = present[u] // (pre + 1), which automatically applies the discount when pre = 1. If u buys, it consumes cost from the budget and earns future[u] - cost, and crucially its own children now see pre = 1. If u does not buy, the children see pre = 0. So:

f[j][pre] = max(nxt[j][0], nxt[j - cost][1] + (future[u] - cost))

The left side means u skips buying (children inherit state 0), and the right side means u buys (children inherit state 1), as long as the budget allows.

The CEO (employee 1) has no boss, so we read the answer from dfs(1)[budget][0], using pre = 0 since there is no one above to grant a discount.

Pattern Learn more about Tree, Depth-First Search and Dynamic Programming patterns.

Solution Approach

We solve this with Tree Dynamic Programming combined with a 0/1 knapsack merge over the budget.

Building the tree. We first construct an adjacency list g, where g[u] holds all the direct subordinates of employee u:

g = [[] for _ in range(n + 1)]
for u, v in hierarchy:
    g[u].append(v)

The DFS state. For each node u, the function dfs(u) returns a (budget + 1) x 2 array f, where f[j][pre] is the maximum profit achievable in the subtree rooted at u when:

the budget is at most j, and
pre is the purchase state of u's direct boss (pre = 1 means the boss bought, pre = 0 means not).

Merging children with a knapsack. Before deciding whether u buys, we combine the results of all children into an array nxt, initialized to all zeros. The budget must be split among the children, so we treat each child as an item in a 0/1 knapsack. For each child v, we get fv = dfs(v) and merge it:

for v in g[u]:
    fv = dfs(v)
    for j in range(budget, -1, -1):
        for jv in range(j + 1):
            for pre in (0, 1):
                val = nxt[j - jv][pre] + fv[jv][pre]
                if val > nxt[j][pre]:
                    nxt[j][pre] = val

Here j is the total budget given to all children processed so far, and jv is the portion allocated to the current child v. We iterate j from high to low so each child is counted only once. The merge follows the formula:

nxt[j][pre] = max(nxt[j][pre], nxt[j - jv][pre] + fv[jv][pre])

After all children are merged, nxt[j][pre] is the best profit from u's subtree excluding u's own decision, given budget j and boss state pre.

Deciding whether u buys. Now we compute f. The cost for u is cost = present[u - 1] // (pre + 1), which is the full price when pre = 0 and the half (discounted) price when pre = 1:

for j in range(budget + 1):
    for pre in (0, 1):
        cost = present[u - 1] // (pre + 1)
        if j >= cost:
            f[j][pre] = max(nxt[j][0], nxt[j - cost][1] + (price - cost))
        else:
            f[j][pre] = nxt[j][0]

Two cases arise:

If j < cost, u cannot afford its stock, so it must skip. Its children then see boss state 0, giving f[j][pre] = nxt[j][0].
If j >= cost, u may either skip or buy:
- Skip: profit is nxt[j][0] (children see boss state 0).
- Buy: profit is nxt[j - cost][1] + (price - cost), where we spend cost, gain future[u] - cost, and children now see boss state 1.
We take the maximum of the two:

f[j][pre] = max(nxt[j][0], nxt[j - cost][1] + (price - cost))

Note that the pre index in f[j][pre] only changes the cost of u itself (through the discount), while the children always branch on u's own buy/skip decision.

The answer. The CEO (employee 1) has no boss, so no discount applies and we read the result with pre = 0:

return dfs(1)[budget][0]

Complexity. Let B be the budget. The knapsack merge at each node costs O(B^2) per child, and summed across the tree this gives an overall time complexity of roughly O(n * B^2). The space used by the DP arrays is O(n * B) across the recursion stack.

Example Walkthrough

Let's trace through a small example to see how the tree DP + knapsack works.

Input:

n = 3
present = [4, 8, 6]
future = [7, 10, 12]
hierarchy = [[1, 2], [1, 3]]
budget = 10

Step 1 — Build the tree.

Employee 1 is the CEO and the direct boss of both 2 and 3:

        1
       / \
      2   3

So the adjacency list is:

g[1] = [2, 3]
g[2] = []
g[3] = []

Step 2 — DFS the leaves first.

We call dfs(1), which recurses into its children before deciding for itself.

dfs(2) (leaf): Employee 2 has no children, so nxt stays all zeros. We compute f for every budget j and every boss-state pre.

For pre = 0 (boss did not buy): cost = present[1] // 1 = 8 // 1 = 8, profit if bought = future[1] - 8 = 10 - 8 = 2.
For pre = 1 (boss bought): cost = present[1] // 2 = 8 // 2 = 4, profit if bought = 10 - 4 = 6.

Filling f[j][pre] = max(nxt[j][0], nxt[j-cost][1] + (price - cost)) (both nxt terms are 0):

`j`	`f[j][0]` (cost 8)	`f[j][1]` (cost 4)
0–3	0	0
4–7	0	6
8–10	2	6

So with the discount (pre=1), employee 2 is far more profitable: a profit of 6 for only 4 spent.

dfs(3) (leaf): Same idea for employee 3.

For pre = 0: cost = present[2] // 1 = 6, profit = future[2] - 6 = 12 - 6 = 6.
For pre = 1: cost = present[2] // 2 = 3, profit = 12 - 3 = 9.

`j`	`f[j][0]` (cost 6)	`f[j][1]` (cost 3)
0–2	0	0
3–5	0	9
6–10	6	9

Again the discounted branch wins: profit 9 for just 3 spent.

Step 3 — Merge children into nxt at node 1.

We start with nxt all zeros, then knapsack-merge dfs(2), then dfs(3).

After merging both children, nxt[j][pre] holds the best combined profit when total budget j is split between employees 2 and 3, all under boss-state pre.

Look at the two states that matter for the CEO's decision:

pre = 0 (CEO does not buy): children pay full price. To buy both we need 8 + 6 = 14 > 10, too much. Best single buy is employee 3 (profit 6, cost 6) or employee 2 (profit 2, cost 8). For j = 10: nxt[10][0] = 6 (buy only 3).
pre = 1 (CEO bought): children get the discount. Employee 2 costs 4 (profit 6), employee 3 costs 3 (profit 9). Buying both costs 4 + 3 = 7 ≤ 10, total profit 6 + 9 = 15. So nxt[j][1] = 15 for j ≥ 7.

Step 4 — Decide whether employee 1 buys.

The CEO has no boss, so we evaluate with pre = 0, where cost = present[0] // 1 = 4, and buying earns future[0] - 4 = 7 - 4 = 3.

At j = budget = 10:

f[10][0] = max(nxt[10][0], nxt[10 - 4][1] + 3) = max(6, nxt[6][1] + 3)

Since nxt[6][1] = 15 (we can afford both discounted children with budget 6: 4 + 3 = 7... actually 7 > 6, so check nxt[6][1]).

Let's be precise. With budget 6 and both children discounted: buying both needs 7, not affordable. Best is buy 2 (cost 4, profit 6) and leftover 2 — can't afford 3 (needs 3). Or buy 3 (cost 3, profit 9) plus leftover 3 — can't afford 2 (needs 4). So nxt[6][1] = 9.

f[10][0] = max(6, 9 + 3) = max(6, 12) = 12

Verifying the winning plan:

CEO buys: spend 4, earn 3. Children now get the discount.
Remaining budget = 6, children see pre = 1.
With 6 left, buy employee 3 (cost 3, earn 9). Remaining 3 — can't afford employee 2 (cost 4).
Total spent: 4 + 3 = 7 ≤ 10. Total profit: 3 + 9 = 12.

Step 5 — Read the answer.

return dfs(1)[budget][0]   # = 12

The maximum profit within the budget is 12. The key insight the DP captures: the CEO buying its own stock (a modest profit of 3) unlocks the discount for the subtree, turning employee 3's purchase from cost-6 into cost-3 and making the whole plan more profitable than skipping the CEO.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def maxProfit(
6        self,
7        n: int,
8        present: List[int],
9        future: List[int],
10        hierarchy: List[List[int]],
11        budget: int,
12    ) -> int:
13        # Build the adjacency list for the tree (1-indexed nodes).
14        # graph[u] holds the direct subordinates (children) of u.
15        graph: List[List[int]] = [[] for _ in range(n + 1)]
16        for parent, child in hierarchy:
17            graph[parent].append(child)
18
19        def dfs(node: int) -> List[List[int]]:
20            # combined[j][parent_bought] = best total profit from the children's
21            # subtrees using budget j, where parent_bought indicates whether
22            # the current `node` ends up buying its own stock (which gives its
23            # children the 50% discount).
24            combined = [[0, 0] for _ in range(budget + 1)]
25
26            for child in graph[node]:
27                child_dp = dfs(child)
28                # Group knapsack: merge each child's dp into combined.
29                # Iterate budget descending to keep a 0/1-style combine per child.
30                for j in range(budget, -1, -1):
31                    for spent in range(j + 1):
32                        for parent_bought in (0, 1):
33                            value = (
34                                combined[j - spent][parent_bought]
35                                + child_dp[spent][parent_bought]
36                            )
37                            if value > combined[j][parent_bought]:
38                                combined[j][parent_bought] = value
39
40            # dp[j][parent_bought] = best profit in this whole subtree with
41            # budget j, where parent_bought tells whether THIS node's parent
42            # bought its stock (so this node may get the discount).
43            dp = [[0, 0] for _ in range(budget + 1)]
44            sell_price = future[node - 1]
45
46            for j in range(budget + 1):
47                for parent_bought in (0, 1):
48                    # Cost of buying this node: half price if the parent bought.
49                    cost = present[node - 1] // (parent_bought + 1)
50                    if j >= cost:
51                        # Option 1: do not buy this node -> children see parent_bought = 0.
52                        # Option 2: buy this node -> children see parent_bought = 1,
53                        #           and we add the profit (sell_price - cost).
54                        dp[j][parent_bought] = max(
55                            combined[j][0],
56                            combined[j - cost][1] + (sell_price - cost),
57                        )
58                    else:
59                        # Not enough budget to buy this node; must skip it.
60                        dp[j][parent_bought] = combined[j][0]
61
62            return dp
63
64        # Root (node 1) has no parent, so parent_bought = 0; use full budget.
65        return dfs(1)[budget][0]
66

1class Solution {
2    // Adjacency list representing the company hierarchy (manager -> subordinates)
3    private List<Integer>[] tree;
4    // present[i]: current price to buy stock for employee i
5    private int[] present;
6    // future[i]: future price of the stock for employee i
7    private int[] future;
8    // Total budget available
9    private int budget;
10
11    public int maxProfit(int n, int[] present, int[] future, int[][] hierarchy, int budget) {
12        this.present = present;
13        this.future = future;
14        this.budget = budget;
15
16        // Initialize the tree with n + 1 nodes (1-indexed employees)
17        tree = new ArrayList[n + 1];
18        Arrays.setAll(tree, k -> new ArrayList<>());
19
20        // Build the hierarchy: e[0] is the manager, e[1] is the subordinate
21        for (int[] edge : hierarchy) {
22            tree[edge[0]].add(edge[1]);
23        }
24
25        // Start DFS from the root (employee 1), return the best profit
26        // using the full budget when the parent did NOT buy (index 0)
27        return dfs(1)[budget][0];
28    }
29
30    /**
31     * Performs a post-order DFS to compute the maximum profit for the subtree rooted at u.
32     *
33     * @param u the current employee node
34     * @return a 2D array dp[j][parentBought] where:
35     *         j            = budget spent on this subtree
36     *         parentBought = 0 if the parent did not buy, 1 if the parent bought
37     *         The value is the maximum profit achievable under these constraints.
38     */
39    private int[][] dfs(int u) {
40        // childrenDp[j][parentBought]: best combined profit from all children
41        // of u using budget j, given whether u (their parent) bought the stock
42        int[][] childrenDp = new int[budget + 1][2];
43
44        // Merge each child's results into childrenDp using a knapsack-style combination
45        for (int child : tree[u]) {
46            int[][] childDp = dfs(child);
47            // Iterate budget in descending order to avoid reusing the same child twice
48            for (int j = budget; j >= 0; j--) {
49                // Allocate jv of the current budget j to this child
50                for (int jv = 0; jv <= j; jv++) {
51                    // Track both states of the parent (u): not bought (0), bought (1)
52                    for (int parentBought = 0; parentBought < 2; parentBought++) {
53                        int candidate = childrenDp[j - jv][parentBought] + childDp[jv][parentBought];
54                        if (candidate > childrenDp[j][parentBought]) {
55                            childrenDp[j][parentBought] = candidate;
56                        }
57                    }
58                }
59            }
60        }
61
62        // dp[j][parentBought]: best profit for the subtree rooted at u
63        int[][] dp = new int[budget + 1][2];
64        int sellPrice = future[u - 1];
65
66        for (int j = 0; j <= budget; j++) {
67            for (int parentBought = 0; parentBought < 2; parentBought++) {
68                // If the parent bought the stock, u gets a 50% discount
69                int cost = present[u - 1] / (parentBought + 1);
70                if (j >= cost) {
71                    // Choice 1: u does NOT buy -> children see parentBought = 0
72                    // Choice 2: u buys -> pay cost, gain (sellPrice - cost),
73                    //           and children see parentBought = 1
74                    dp[j][parentBought] = Math.max(
75                        childrenDp[j][0],
76                        childrenDp[j - cost][1] + (sellPrice - cost)
77                    );
78                } else {
79                    // Not enough budget for u to buy, so u must skip
80                    dp[j][parentBought] = childrenDp[j][0];
81                }
82            }
83        }
84
85        return dp;
86    }
87}
88

1class Solution {
2public:
3    int maxProfit(int n, vector<int>& present, vector<int>& future,
4                  vector<vector<int>>& hierarchy, int budget) {
5        // Build the adjacency list representing the company hierarchy.
6        // children[u] holds all direct subordinates of employee u.
7        vector<vector<int>> children(n + 1);
8        for (auto& edge : hierarchy) {
9            int parent = edge[0];
10            int child = edge[1];
11            children[parent].push_back(child);
12        }
13
14        // dfs returns a DP table for the subtree rooted at node u.
15        // The returned table 'result' is indexed as result[j][prev]:
16        //   j    -> the amount of budget allowed for this subtree
17        //   prev -> whether the parent of u was bought (0 = not bought, 1 = bought)
18        // The stored value is the maximum profit achievable under these constraints.
19        auto dfs = [&](const auto& dfs, int u) -> vector<array<int, 2>> {
20            // 'merged' aggregates the best profit obtainable by distributing
21            // budget among all children of u. merged[j][prev] is the max profit
22            // using budget j across processed children, given parent-bought state.
23            vector<array<int, 2>> merged(budget + 1);
24            for (int j = 0; j <= budget; j++) {
25                merged[j] = {0, 0};
26            }
27
28            // Combine each child's DP table into 'merged' via a knapsack merge.
29            for (int child : children[u]) {
30                auto childDp = dfs(dfs, child);
31
32                // Iterate budget from high to low to avoid reusing the same
33                // child's allocation more than once (standard 0/1 knapsack order).
34                for (int j = budget; j >= 0; j--) {
35                    // Try giving 'spend' budget to the current child.
36                    for (int spend = 0; spend <= j; spend++) {
37                        for (int prev = 0; prev < 2; prev++) {
38                            int candidate = merged[j - spend][prev] + childDp[spend][prev];
39                            if (candidate > merged[j][prev]) {
40                                merged[j][prev] = candidate;
41                            }
42                        }
43                    }
44                }
45            }
46
47            // Build the DP table for node u using the merged children result.
48            vector<array<int, 2>> result(budget + 1);
49            int sellingPrice = future[u - 1];
50
51            for (int j = 0; j <= budget; j++) {
52                for (int prev = 0; prev < 2; prev++) {
53                    // If the parent was bought (prev == 1), u gets a discount,
54                    // so its purchase cost is halved (present / 2); otherwise full price.
55                    int cost = present[u - 1] / (prev + 1);
56
57                    if (j >= cost) {
58                        // Two choices:
59                        //   1. Skip buying u: children see prev = 0, full budget j.
60                        //   2. Buy u: pay 'cost', children see prev = 1 with budget j - cost,
61                        //      and we gain profit (sellingPrice - cost).
62                        result[j][prev] = max(
63                            merged[j][0],
64                            merged[j - cost][1] + (sellingPrice - cost));
65                    } else {
66                        // Not enough budget to buy u; only the skip option is valid.
67                        result[j][prev] = merged[j][0];
68                    }
69                }
70            }
71
72            return result;
73        };
74
75        // The root (employee 1) has no parent, so prev = 0 (parent not bought).
76        return dfs(dfs, 1)[budget][0];
77    }
78};
79

1/**
2 * Computes the maximum profit obtainable by purchasing stocks within a budget,
3 * where buying a parent's stock grants the child a 50% discount on its price.
4 *
5 * @param n - Number of employees (nodes), labeled 1..n.
6 * @param present - present[i] is the current price of node (i + 1).
7 * @param future - future[i] is the future price of node (i + 1).
8 * @param hierarchy - Edges [u, v] meaning u is the direct superior of v.
9 * @param budget - Total money available to spend.
10 * @returns The maximum achievable profit.
11 */
12function maxProfit(
13    n: number,
14    present: number[],
15    future: number[],
16    hierarchy: number[][],
17    budget: number,
18): number {
19    // Adjacency list: children[u] holds the direct subordinates of node u.
20    const children: number[][] = Array.from({ length: n + 1 }, () => []);
21
22    for (const [superior, subordinate] of hierarchy) {
23        children[superior].push(subordinate);
24    }
25
26    /**
27     * Depth-first search returning a DP table for the subtree rooted at `node`.
28     *
29     * The returned table `dp` is indexed as dp[spent][discounted], where:
30     *   - spent: amount of budget allocated to this subtree (0..budget).
31     *   - discounted: 0 if this node is bought at full price (parent not bought),
32     *                 1 if this node is eligible for the 50% discount (parent bought).
33     *
34     * dp[spent][discounted] is the maximum profit for this subtree using at most
35     * `spent` budget under the given discount condition.
36     */
37    const dfs = (node: number): number[][] => {
38        // mergedChildren[j][discounted]: best combined profit from already-processed
39        // children using exactly up to budget j, with the current node's discount state.
40        const mergedChildren: number[][] = Array.from(
41            { length: budget + 1 },
42            () => [0, 0],
43        );
44
45        // Merge each child's DP table into mergedChildren via a knapsack combination.
46        for (const child of children[node]) {
47            const childDp = dfs(child);
48
49            // Iterate budget downward to avoid reusing the same child multiple times.
50            for (let j = budget; j >= 0; j--) {
51                for (let childSpent = 0; childSpent <= j; childSpent++) {
52                    for (let discounted = 0; discounted < 2; discounted++) {
53                        mergedChildren[j][discounted] = Math.max(
54                            mergedChildren[j][discounted],
55                            mergedChildren[j - childSpent][discounted] +
56                                childDp[childSpent][discounted],
57                        );
58                    }
59                }
60            }
61        }
62
63        // Build this node's DP table by deciding whether to buy its stock.
64        const dp: number[][] = Array.from({ length: budget + 1 }, () => [0, 0]);
65        const sellPrice = future[node - 1];
66
67        for (let j = 0; j <= budget; j++) {
68            for (let discounted = 0; discounted < 2; discounted++) {
69                // Cost is halved (floored) when the parent has been bought (discounted = 1).
70                const cost = Math.floor(present[node - 1] / (discounted + 1));
71
72                if (j >= cost) {
73                    // If we buy this node, children become eligible for the discount (index 1).
74                    const profitIfBuy =
75                        mergedChildren[j - cost][1] + (sellPrice - cost);
76                    // Otherwise children stay at full price (index 0).
77                    dp[j][discounted] = Math.max(mergedChildren[j][0], profitIfBuy);
78                } else {
79                    // Not enough budget to buy this node; children stay at full price.
80                    dp[j][discounted] = mergedChildren[j][0];
81                }
82            }
83        }
84
85        return dp;
86    };
87
88    // The root (node 1) has no parent, so it is at full price (discounted = 0).
89    return dfs(1)[budget][0];
90}
91

Time and Space Complexity

Time Complexity: O(n × budget²)

The code performs a tree DP via the dfs function, which is called once for each of the n nodes (since the hierarchy forms a tree rooted at node 1).

For each node u, the merging of children's DP results runs a nested loop:
```
for j in range(budget, -1, -1):
    for jv in range(j + 1):
        for pre in (0, 1):
            ...
```
The outer loop runs budget + 1 times and the inner loop runs up to j + 1 times, giving O(budget²) work per child. A subtle but crucial point: when summing this knapsack-merge cost over all edges across the entire tree, the total work is bounded by O(n × budget²). This is because each node is merged into its parent exactly once, so the merging cost is distributed across the n - 1 edges, contributing O(n × budget²) overall.
The second loop in each dfs call computes f and runs O(budget) times per node, contributing O(n × budget) in total, which is dominated by the merging cost.

Therefore, the total time complexity is O(n × budget²).

Space Complexity: O(n × budget)

Each call to dfs allocates the arrays nxt and f, each of size O(budget).
Due to the recursion, multiple dfs frames can be active simultaneously along a path from the root to a leaf. In the worst case (a degenerate chain-like tree), the recursion depth reaches O(n), and each frame holds O(budget) space.
This yields a stack-related space usage of O(n × budget).

Additionally, the adjacency list g requires O(n) space. The dominant term is the recursion stack, so the overall space complexity is O(n × budget).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Iterating the knapsack budget in ascending order (item reuse)

The most frequent mistake in the group-knapsack merge is iterating the total budget j in ascending order instead of descending order. Although the merge here reads from a separate child_dp array (rather than the same array being written, as in a classic 1D knapsack), the subtle danger appears when people try to "optimize" by collapsing combined into the merge in place, or when they reverse the loop directions out of habit.

The correct loop must process j from high to low so that the combined[j - spent] value used as a base never already includes the current child's contribution:

for j in range(budget, -1, -1):       # CORRECT: descending
    for spent in range(j + 1):
        ...

If you write for j in range(budget + 1): (ascending) and you ever change combined[j - spent] to refer to an updated value of the same child, you would let one child be allocated budget multiple times, inflating profit. Keep the descending order as a defensive habit, and never write back into a slot you will read again for the same child.

Pitfall 2: Forgetting that `pre` only affects `node`'s own cost, not its children

A very common conceptual error is to propagate the parent_bought flag straight through to the children. People mistakenly write:

# WRONG
dp[j][parent_bought] = max(
    combined[j][parent_bought],                       # wrong index
    combined[j - cost][parent_bought] + (sell_price - cost),
)

The flag parent_bought describes whether this node's boss bought, which only changes this node's discounted cost. What the children care about is whether this node itself bought. Therefore:

The skip branch must read combined[j][0] (this node did not buy → children get no discount).
The buy branch must read combined[j - cost][1] (this node bought → children get the discount).

Using parent_bought as the index into combined mixes up two different "who bought" questions and produces wrong answers on any tree deeper than two levels.

Pitfall 3: Computing the discounted cost incorrectly

The discount is floor(present[v] / 2), elegantly expressed as present[node - 1] // (parent_bought + 1):

parent_bought = 0 → divide by 1 → full price.
parent_bought = 1 → divide by 2 → floored half price.

Pitfalls here include:

Applying the discount with present[node - 1] / 2 (true division) instead of // (floor division), which yields a float and breaks integer budget comparisons.
Applying the discount to the selling price future as well — only the buying cost is discounted; sell_price is always future[node - 1].
Off-by-one indexing: arrays are described as 1-based in the statement but stored 0-based, so the node's own data is at present[node - 1] / future[node - 1].

Pitfall 4: Recursion depth and performance on large/deep trees

dfs is recursive, and a degenerate "chain" tree (each boss has exactly one subordinate) reaches depth n. For large n this can hit Python's default recursion limit. Mitigations:

import sys
sys.setrecursionlimit(n + 10)

Additionally, the O(n · B²) knapsack can be slow for large budgets. A practical optimization is to cap the inner spent loop by the budget actually consumable in the child's subtree, or to track each subtree's maximum useful spend and avoid iterating past it — this prunes the quadratic merge significantly when subtrees are small.

Pitfall 5: Reading the final answer with the wrong flag

The CEO (node 1) has no boss, so no discount can ever apply to it. The answer must be read with parent_bought = 0:

return dfs(1)[budget][0]   # CORRECT

Reading dfs(1)[budget][1] would incorrectly grant the CEO a phantom half-price discount that has no parent to justify it, overstating the profit.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know

Core Learning

LLD/OOP Interview

Live Training

Additional Resources

AI Engineering