Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

An employee's price depends only on whether their direct manager buys. After fixing that choice, child subtrees are independent except for sharing the budget. Use a tree knapsack with two parent-purchase states and merge the children's possible budget allocations.

Approach

For each employee, return two arrays of best profit within each budget: one when their parent does not buy, and one when their parent does. First merge all child subtrees twice, once assuming this employee skips buying and once assuming this employee buys. A merge tries all ways to split a budget between accumulated children and the next child.

For either parent state, skipping this employee uses the children's no-discount result. Buying uses the children's discounted result, spends this employee's applicable price, and adds future - price. The price is full when the parent skips and halved with floor division when the parent buys. Keep the better option for each budget.

Return the root's no-parent-purchase state at the full budget. Buying at a personal loss is still considered because it may unlock larger descendant gains. Future proceeds are profit, not extra purchasing budget.

def merge(a, b):
    n = len(a)
    arr = [0] * n

    for i in range(n):
        for j in range(n - i):
            # if i + j >= n:
            #     break
            arr[i + j] = max(arr[i + j], a[i] + b[j])

    return arr

class Solution:
    def maxProfit(self, n: int, present: List[int], future: List[int], hierarchy: List[List[int]], budget: int) -> int:
        adj = defaultdict(list)

        for a, b in hierarchy:
            adj[a - 1].append(b - 1)

        def dfs(node):
            dp0 = [0] * (budget + 1)
            dp1 = [0] * (budget + 1)

            for nei in adj[node]:
                nei0, nei1 = dfs(nei)
                dp0 = merge(dp0, nei0)
                dp1 = merge(dp1, nei1)

            copy0 = dp0[:]
            copy1 = dp0[:]
            cost = present[node]

            for b in range(cost, budget + 1):
                copy0[b] = max(copy0[b], dp1[b - cost] + future[node] - cost)

            cost //= 2

            for b in range(cost, budget + 1):
                copy1[b] = max(copy1[b], dp1[b - cost] + future[node] - cost)

            return copy0, copy1

        return dfs(0)[0][-1]

Complexity analysis

Let N be the employee count and B the budget. Time: O(N * B^2) for child knapsack merges. Auxiliary space: O(N * B) in the worst case for returned subtree DP arrays and recursion.