Employee Hierarchy FTE Score and Capacity-Constrained Insertion

Implement an employee hierarchy manager. Every employee has a unique eid, and all employees form a rooted reporting tree with the CEO as its root. Define the FTE score of employee eid as the number of employees in that employee's subtree, including the employee themself, all direct reports, and all indirect reports. Each employee can have at most k direct reports. Support these operations: SCORE eid: Print the FTE score of eid. ADD new_eid manager_eid: Insert a new employee into manager_eid's organization. First try to attach the employee directly to manager_eid. If that manager already has k direct reports, search downward through that manager's organization level by level (BFS) for an employee with fewer than k direct reports, and attach the new employee there. The original interview did not require an ordering among candidates on the same level. For deterministic output here, visit children in their insertion order. Print the eid of the actual direct manager selected. PARENT eid: Print the direct manager of eid; print -1 for the CEO. Input format: n k q n lines: eid parent_eid q operation lines The initial n employees form a valid tree; the CEO has parent_eid = -1. The initial hierarchy satisfies the limit of at most k direct reports per employee. In ADD, new_eid is guaranteed not to exist and manager_eid is guaranteed to exist. 1 <= n, q <= 2 * 10^5, 1 <= k <= 2 * 10^5. Example: Input: 3 2 5 1 -1 2 1 3 1 SCORE 1 ADD 4 1 SCORE 1 PARENT 4 SCORE 2 Output: 3 2 4 2 Implement a baseline solution and explain how insertion lookup and FTE-score updates can be optimized. Example Input 3 2 5 1 -1 2 1 3 1 SCORE 1 ADD 4 1 SCORE 1 PARENT 4 SCORE 2 Output 3 2 4 2