FastPrep
Problem · Tree

Maximize Happiness

Learn this problem
● HardRubrikOA

Problem statement

Employees form a rooted company tree. Row i of employeeData is [manager, cost, leadership] for employee i + 1. Manager 0 marks the root.

Choose one employee as the manager for a client, then hire any subset of employees in that manager's subtree. The chosen manager may be hired, but does not have to be. The total hiring cost must not exceed budget.

The client's happiness is:

chosen manager's leadership * number of hired employees.

Return the maximum possible happiness.

Function

maximizeHappiness(employeeData: int[][], budget: int) → long

Examples

Example 1

employeeData = [[0, 10, 400], [1, 10, 300], [2, 15, 100], [1, 10, 60], [1, 15, 800], [2, 5, 100], [2, 5, 100]]budget = 20return = 1200

Choose employee 1 as manager and hire employees 2, 6, 7. Their total cost is 20, so happiness is 400 * 3 = 1200.

Constraints

  • 1 <= T <= 10
  • 1 <= N <=100 000 The number of Employees
  • 1 <= M <=1 000 000 000 The budget
  • 0 <= R[i] < i The RM for each employee
  • 1 <= C[i] <= M The amount of cost of each employee
  • 1 <= L[i] <= 1 000 000 000 The leadership level of each employee
  • Subtask 1: N <= 10
  • Subtask 2: N <= 3000
  • Subtask 3: Original

    • More Rubrik problems

    drafts saved locally
    public long maximizeHappiness(int[][] employeeData, int budget) {
  // write your code here
}
    employeeData[[0, 10, 400], [1, 10, 300], [2, 15, 100], [1, 10, 60], [1, 15, 800], [2, 5, 100], [2, 5, 100]]
    budget20
    expected1200
    checking account