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. You are given two 1-based integer arrays, present and future, each of length n, where: prese

maxProfit.js

/**
 * @param {number} n
 * @param {number[]} present
 * @param {number[]} future
 * @param {number[][]} hierarchy
 * @param {number} budget
 * @return {number}
 */
var maxProfit = function(n, present, future, hierarchy, budget) {
  const employeeCount = n;
  const budgetLimit = budget;
  const budgetStride = budgetLimit + 1;

  // Sentinel value for unreachable DP states
  const MIN_PROFIT = -1_000_000_000;

  // Price arrays (1-indexed by employee ID for convenience)
  const presentPrice = new Int32Array(employeeCount + 1);
  const futurePrice = new Int32Array(employeeCount + 1);
  const discountedPrice = new Int32Array(employeeCount + 1);

  // Initialize price arrays
  for (let id = 1; id <= employeeCount; id++) {
    presentPrice[id] = present[id - 1];
    futurePrice[id] = future[id - 1];
    discountedPrice[id] = presentPrice[id] >> 1; // floor(present/2)
  }

  // -------------------------------
  // Build adjacency list for hierarchy
  // -------------------------------
  const headEdgeIndex = new Int32Array(employeeCount + 1).fill(-1);
  const toEmployee = new Int32Array(employeeCount - 1);
  const nextEdgeIndex = new Int32Array(employeeCount - 1);

  for (let i = 0; i < hierarchy.length; i++) {
    const boss = hierarchy[i][0];
    const child = hierarchy[i][1];
    toEmployee[i] = child;
    nextEdgeIndex[i] = headEdgeIndex[boss];
    headEdgeIndex[boss] = i;
  }

  // -------------------------------
  // Generate preorder traversal (iterative DFS)
  // -------------------------------
  const stack = new Int32Array(employeeCount);
  let stackSize = 0;
  const preorder = new Int32Array(employeeCount);
  let preorderSize = 0;

  stack[stackSize++] = 1; // start from CEO

  while (stackSize > 0) {
    const node = stack[--stackSize];
    preorder[preorderSize++] = node;

    // Push children
    for (let edge = headEdgeIndex[node]; edge !== -1; edge = nextEdgeIndex[edge]) {
      stack[stackSize++] = toEmployee[edge];
    }
  }

  // -------------------------------
  // DP array:
  // dp[(employeeId * 2 + parentBoughtFlag) * budgetStride + spent] = max profit
  // parentBoughtFlag = 0 (parent not bought), 1 (parent bought)
  // -------------------------------
  const dp = new Int32Array((employeeCount + 1) * 2 * budgetStride).fill(MIN_PROFIT);

  // Buffers for merging children’s contributions
  const childrenProfitWhenNotBought = new Int32Array(budgetStride);
  const childrenProfitWhenBought = new Int32Array(budgetStride);
  const mergeBuffer = new Int32Array(budgetStride);

  // -------------------------------
  // Process nodes bottom-up (reverse preorder = postorder)
  // -------------------------------
  for (let idx = preorderSize - 1; idx >= 0; idx--) {
    const employeeId = preorder[idx];

    // Reset child aggregation arrays
    childrenProfitWhenNotBought.fill(MIN_PROFIT);
    childrenProfitWhenBought.fill(MIN_PROFIT);
    childrenProfitWhenNotBought[0] = 0;
    childrenProfitWhenBought[0] = 0;

    // Merge contributions from each child
    for (let edge = headEdgeIndex[employeeId]; edge !== -1; edge = nextEdgeIndex[edge]) {
      const childId = toEmployee[edge];

      // Case: current employee NOT bought → child sees parentBought = false
      mergeBuffer.fill(MIN_PROFIT);
      const childBaseNotBought = (childId << 1) * budgetStride;

      for (let spentSoFar = 0; spentSoFar <= budgetLimit; spentSoFar++) {
        const currentProfit = childrenProfitWhenNotBought[spentSoFar];
        if (currentProfit === MIN_PROFIT) continue;

        const remainingBudget = budgetLimit - spentSoFar;
        for (let childSpent = 0; childSpent <= remainingBudget; childSpent++) {
          const childProfit = dp[childBaseNotBought + childSpent];
          if (childProfit === MIN_PROFIT) continue;

          const totalSpent = spentSoFar + childSpent;
          const totalProfit = currentProfit + childProfit;
          if (totalProfit > mergeBuffer[totalSpent]) {
            mergeBuffer[totalSpent] = totalProfit;
          }
        }
      }
      childrenProfitWhenNotBought.set(mergeBuffer);

      // Case: current employee IS bought → child sees parentBought = true
      mergeBuffer.fill(MIN_PROFIT);
      const childBaseBought = childBaseNotBought + budgetStride;

      for (let spentSoFar = 0; spentSoFar <= budgetLimit; spentSoFar++) {
        const currentProfit = childrenProfitWhenBought[spentSoFar];
        if (currentProfit === MIN_PROFIT) continue;

        const remainingBudget = budgetLimit - spentSoFar;
        for (let childSpent = 0; childSpent <= remainingBudget; childSpent++) {
          const childProfit = dp[childBaseBought + childSpent];
          if (childProfit === MIN_PROFIT) continue;

          const totalSpent = spentSoFar + childSpent;
          const totalProfit = currentProfit + childProfit;
          if (totalProfit > mergeBuffer[totalSpent]) {
            mergeBuffer[totalSpent] = totalProfit;
          }
        }
      }
      childrenProfitWhenBought.set(mergeBuffer);
    }

    // Base indices for DP states
    const nodeBaseParentNotBought = (employeeId << 1) * budgetStride;
    const nodeBaseParentBought = nodeBaseParentNotBought + budgetStride;

    // Case: skip current employee → profit comes only from children
    for (let spent = 0; spent <= budgetLimit; spent++) {
      const inheritedProfit = childrenProfitWhenNotBought[spent];
      dp[nodeBaseParentNotBought + spent] = inheritedProfit;
      dp[nodeBaseParentBought + spent] = inheritedProfit;
    }

    // Case: buy current employee
    const normalCost = presentPrice[employeeId];
    const discountedCost = discountedPrice[employeeId];
    const normalProfit = futurePrice[employeeId] - normalCost;
    const discountedProfit = futurePrice[employeeId] - discountedCost;

    // Parent NOT bought → pay full price
    for (let spent = normalCost; spent <= budgetLimit; spent++) {
      const childrenSpent = spent - normalCost;
      const childrenProfit = childrenProfitWhenBought[childrenSpent];
      if (childrenProfit === MIN_PROFIT) continue;

      const candidateProfit = childrenProfit + normalProfit;
      if (candidateProfit > dp[nodeBaseParentNotBought + spent]) {
        dp[nodeBaseParentNotBought + spent] = candidateProfit;
      }
    }

    // Parent bought → pay discounted price
    for (let spent = discountedCost; spent <= budgetLimit; spent++) {
      const childrenSpent = spent - discountedCost;
      const childrenProfit = childrenProfitWhenBought[childrenSpent];
      if (childrenProfit === MIN_PROFIT) continue;

      const candidateProfit = childrenProfit + discountedProfit;
      if (candidateProfit > dp[nodeBaseParentBought + spent]) {
        dp[nodeBaseParentBought + spent] = candidateProfit;
      }
    }
  }

  // -------------------------------
  // Extract best profit from CEO’s DP states
  // CEO has no parent, so parentBoughtFlag = 0
  // -------------------------------
  const rootBase = (1 << 1) * budgetStride;
  let bestProfit = 0;
  for (let spent = 0; spent <= budgetLimit; spent++) {
    bestProfit = Math.max(bestProfit, dp[rootBase + spent]);
  }

  return bestProfit;
};