Solution: Dynamic Programming

Task

Imagine you’ve just been appointed as the new organizer of the first annual mandatory holiday party at Giggle (a subsidiary of Abugida). Giggle employees are organized into a strict hierarchy—a tree with the company president at the root. The all-knowing oracles in Human Resources have assigned a real number to each employee measuring how “fun” the employee is. To keep things social, there is one restriction on the guest list: an employee cannot attend the party if their immediate supervisor is also present. On the other hand, the president of the company must attend the party, even though she has a negative fun rating; it’s her company, after all.

Given an algorithm that makes a guest list for the party that maximizes the sum of the “fun” ratings of the guests, write the code in the coding playground.

Logic building

Before jumping to the coding implementation. let’s understand the algorithm to solve this problem.

We can use a dynamic programming approach! We’ll represent the employee hierarchy as a tree where each node contains the employee’s fun rating. The algorithm will be based on a recursive function that traverses the tree and calculates the maximum fun for each subtree, considering two cases: when the root of the subtree is included in the guest list and when it’s excluded.

Here’s a step-by-step algorithm to make a guest list for the party:

• Create a function $max$_$fun(node)$ that takes a tree node as input. This node represents an employee and contains the employee’s fun rating and a list of children nodes (subordinates).
• Base case: If the given node is null (no employee),

...