3562. Maximum Profit from Trading Stocks with Discounts Hard

1/**
2 * [3562] Maximum Profit from Trading Stocks with Discounts
3 *
4 * You are given an integer n, representing the number of employees in a company. Each employee is assigned a unique ID from 1 to n, and employee 1 is the CEO, is the direct or indirect boss of every employee. You are given two 1-based integer arrays, present and future, each of length n, where:
5 * 
6 * 	present[i] represents the current price at which the i^th employee can buy a stock today.
7 * 	future[i] represents the expected price at which the i^th employee can sell the stock tomorrow.
8 * 
9 * The company's hierarchy is represented by a 2D integer array hierarchy, where hierarchy[i] = [ui, vi] means that employee ui is the direct boss of employee vi.
10 * Additionally, you have an integer budget representing the total funds available for investment.
11 * However, the company has a discount policy: if an employee's direct boss purchases their own stock, then the employee can buy their stock at half the original price (floor(present[v] / 2)).
12 * Return the maximum profit that can be achieved without exceeding the given budget.
13 * Note:
14 * 
15 * 	You may buy each stock at most once.
16 * 	You cannot use any profit earned from future stock prices to fund additional investments and must buy only from budget.
17 * 
18 *  
19 * <strong class="example">Example 1:
20 * <div class="example-block">
21 * Input: <span class="example-io">n = 2, present = [1,2], future = [4,3], hierarchy = [[1,2]], budget = 3</span>
22 * Output: <span class="example-io">5</span>
23 * Explanation:
24 * <img src="https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-053641.png" style="width: 200px; height: 80px;" />
25 * 
26 * 	Employee 1 buys the stock at price 1 and earns a profit of 4 - 1 = 3.
27 * 	Since Employee 1 is the direct boss of Employee 2, Employee 2 gets a discounted price of floor(2 / 2) = 1.
28 * 	Employee 2 buys the stock at price 1 and earns a profit of 3 - 1 = 2.
29 * 	The total buying cost is 1 + 1 = 2 <= budget. Thus, the maximum total profit achieved is 3 + 2 = 5.
30 * </div>
31 * <strong class="example">Example 2:
32 * <div class="example-block">
33 * Input: <span class="example-io">n = 2, present = [3,4], future = [5,8], hierarchy = [[1,2]], budget = 4</span>
34 * Output: <span class="example-io">4</span>
35 * Explanation:
36 * <img src="https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-053641.png" style="width: 200px; height: 80px;" />
37 * 
38 * 	Employee 2 buys the stock at price 4 and earns a profit of 8 - 4 = 4.
39 * 	Since both employees cannot buy together, the maximum profit is 4.
40 * </div>
41 * <strong class="example">Example 3:
42 * <div class="example-block">
43 * Input: <span class="example-io">n = 3, present = [4,6,8], future = [7,9,11], hierarchy = [[1,2],[1,3]], budget = 10</span>
44 * Output: 10
45 * Explanation:
46 * <img src="https://assets.leetcode.com/uploads/2025/04/09/image.png" style="width: 180px; height: 153px;" />
47 * 
48 * 	Employee 1 buys the stock at price 4 and earns a profit of 7 - 4 = 3.
49 * 	Employee 3 would get a discounted price of floor(8 / 2) = 4 and earns a profit of 11 - 4 = 7.
50 * 	Employee 1 and Employee 3 buy their stocks at a total cost of 4 + 4 = 8 <= budget. Thus, the maximum total profit achieved is 3 + 7 = 10.
51 * </div>
52 * <strong class="example">Example 4:
53 * <div class="example-block">
54 * Input: <span class="example-io">n = 3, present = [5,2,3], future = [8,5,6], hierarchy = [[1,2],[2,3]], budget = 7</span>
55 * Output: <span class="example-io">12</span>
56 * Explanation:
57 * <img src="https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-054114.png" style="width: 300px; height: 85px;" />
58 * 
59 * 	Employee 1 buys the stock at price 5 and earns a profit of 8 - 5 = 3.
60 * 	Employee 2 would get a discounted price of floor(2 / 2) = 1 and earns a profit of 5 - 1 = 4.
61 * 	Employee 3 would get a discounted price of floor(3 / 2) = 1 and earns a profit of 6 - 1 = 5.
62 * 	The total cost becomes 5 + 1 + 1 = 7 <= budget. Thus, the maximum total profit achieved is 3 + 4 + 5 = 12.
63 * </div>
64 *  
65 * Constraints:
66 * 
67 * 	1 <= n <= 160
68 * 	present.length, future.length == n
69 * 	1 <= present[i], future[i] <= 50
70 * 	hierarchy.length == n - 1
71 * 	hierarchy[i] == [ui, vi]
72 * 	1 <= ui, vi <= n
73 * 	ui != vi
74 * 	1 <= budget <= 160
75 * 	There are no duplicate edges.
76 * 	Employee 1 is the direct or indirect boss of every employee.
77 * 	The input graph hierarchy is guaranteed to have no cycles.
78 * 
79 */
80pub struct Solution {}
81
82// problem: https://leetcode.com/problems/maximum-profit-from-trading-stocks-with-discounts/
83// discuss: https://leetcode.com/problems/maximum-profit-from-trading-stocks-with-discounts/discuss/?currentPage=1&orderBy=most_votes&query=
84
85// submission codes start here
86
87impl Solution {
88    pub fn max_profit(n: i32, present: Vec<i32>, future: Vec<i32>, hierarchy: Vec<Vec<i32>>, budget: i32) -> i32 {
89        0
90    }
91}
92
93// submission codes end
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn test_3562() {
101    }
102}
103