3562. Maximum Profit from Trading Stocks with Discounts

Difficulty: Hard
Topics: Dynamic Programming, Tree DP, Knapsack, Graph Theory

---

Problem

You are given an integer n, representing the number of employees in a company.
Each employee has a unique ID from 1 to n, and employee 1 is the CEO.

You are given two 1-based arrays:

• present[i] → today's price at which employee i can buy stock
• future[i] → tomorrow's selling price for employee i

You are also given a hierarchy array of edges:

• hierarchy[i] = [u, v] means employee u is the direct boss of employee v

There is a total budget representing the amount available for buying stocks.

---

Discount Rule

If a boss buys stock, then each of their direct subordinates can buy stock at half price:

$$text{discountPrice}[v] = leftlfloor frac{text{present}[v]}{2} rightrfloor$$

You may buy each employee’s stock at most once, and you cannot reuse the profit from selling to buy more stocks.

---

Goal

Return the maximum total profit achievable without exceeding the budget.

Profit for employee i:

$text{future}[i] - text{cost}[i]$

Examples

Example 1

Input:

n = 2  
present = [1, 2]  
future = [4, 3]  
hierarchy = [[1, 2]]  
budget = 3

Output:

5

Explanation:

• Employee 1 buys → cost = 1, profit = 3
• Employee 2 gets discount → cost = 1, profit = 2
• Total cost = 2 ≤ 3
• Total profit = 3 + 2 = 5

---

Example 2

Input:

n = 2  
present = [3, 4]  
future = [5, 8]  
hierarchy = [[1, 2]]  
budget = 4

Output:

4

Explanation:

Only Employee 2 can buy within budget → profit = 4.

---

Example 3

Input:

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

Output:

10

Explanation:

• Employee 1 buys → cost = 4, profit = 3
• Employee 3 gets discount → cost = 4, profit = 7
• Total cost = 8 ≤ 10
• Total profit = 10

---

Example 4

Input:

n = 3  
present = [5, 2, 3]  
future = [8, 5, 6]  
hierarchy = [[1, 2], [2, 3]]  
budget = 7

Output:

12

Explanation:

• Employee 1 buys → cost = 5, profit = 3
• Employee 2 gets discount → cost = 1, profit = 4
• Employee 3 gets discount → cost = 1, profit = 5
• Total cost = 7 ≤ 7
• Total profit = 12

---

Constraints

1 <= n <= 160
1 <= present[i], future[i] <= 50
1 <= budget <= 160
hierarchy.length = n - 1
Employee 1 is root of the hierarchy tree
No cycles in the hierarchy

import java.util.*;

public class Main { public static class Result { int[] dp0; int[] dp1; int size;

Result(int[] dp0, int[] dp1, int size) {
    this.dp0 = dp0;
    this.dp1 = dp1;
    this.size = size;
}

} public static void main(String[] args) { // Example Input int n = 3; int[] present = {5, 2, 3}; int[] future = {8, 5, 6}; int[][] hierarchy = { {1, 2}, {2, 3} }; int budget = 7;

    int ans = maxProfit(n, present, future, hierarchy, budget);

    System.out.println("Maximum Profit = " + ans);
}

public static int maxProfit(
        int n,
        int[] present,
        int[] future,
        int[][] hierarchy,
        int budget
) {
    List<Integer>[] g = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        g[i] = new ArrayList<>();
    }
    for (int[] e : hierarchy) {
        g[e[0] - 1].add(e[1] - 1);
    }

    return dfs(0, present, future, g, budget).dp0[budget];
}

private static Result dfs(
        int u,
        int[] present,
        int[] future,
        List<Integer>[] g,
        int budget
) {
    int cost = present[u];
    int dCost = present[u] / 2;

    int[] dp0 = new int[budget + 1];
    int[] dp1 = new int[budget + 1];

    int[] subProfit0 = new int[budget + 1];
    int[] subProfit1 = new int[budget + 1];

    int uSize = cost;

    for (int v : g[u]) {
        Result childResult = dfs(v, present, future, g, budget);
        uSize += childResult.size;

        for (int i = budget; i >= 0; i--) {
            for (int sub = 0; sub <= Math.min(childResult.size, i); sub++) {
                if (i - sub >= 0) {
                    subProfit0[i] = Math.max(
                            subProfit0[i],
                            subProfit0[i - sub] + childResult.dp0[sub]
                    );
                    subProfit1[i] = Math.max(
                            subProfit1[i],
                            subProfit1[i - sub] + childResult.dp1[sub]
                    );
                }
            }
        }
    }

    for (int i = 0; i <= budget; i++) {
        dp0[i] = subProfit0[i];
        dp1[i] = subProfit0[i];

        if (i >= dCost) {
            dp1[i] = Math.max(
                    dp1[i],
                    subProfit1[i - dCost] + future[u] - dCost
            );
        }
        if (i >= cost) {
            dp0[i] = Math.max(
                    dp0[i],
                    subProfit1[i - cost] + future[u] - cost
            );
        }
    }

    return new Result(dp0, dp1, uSize);
}

}