The Corporate Hierarchy Problem

January 9, 2026 • 6 min read

In systems engineering, we often deal with dependencies. Service A calls Service B, which calls Service C. In the corporate world, it’s an Org Chart.

The problem CSES 1674: Subordinates asks a deceptively simple question: Given a company structure, calculate how many subordinates each employee has.

Not just direct reports—everyone down the chain.

The Input

We are given $N$ employees ($2 \le N \le 200,000$). Employee 1 is the General Director (Root). For every other employee $i$, we are told who their direct boss is.

5          (Total employees)
1 1 2 3    (Bosses for employees 2, 3, 4, 5)

Step 1: Modeling the Data

The input gives us the data as a list of parents:

Employee 2’s boss is 1.
Employee 3’s boss is 1.
Employee 4’s boss is 2.
Employee 5’s boss is 3.

If we store it exactly like this (an array where parent[i] = boss), we have a problem. To find out who reports to Employee 1, we have to scan the entire array to check who lists “1” as their boss. This is inefficient.

The Right Structure: Adjacency List

We need to invert the relationship. Instead of “Who is my boss?”, we need to answer “Who is on my team?”.

We represent this as a Directed Graph (specifically a Tree) using an Adjacency List. adj[Boss] = [Employee A, Employee B, ...]

For our example:

adj[1] -> [2, 3]
adj[2] -> [4]
adj[3] -> [5]
adj[4] -> []
adj[5] -> []

Step 2: The Brute Force Trap

The naive instinct is to simulate the counting process for each person individually.

// Pseudocode for Brute Force
for each employee i from 1 to N:
    count = 0
    queue = [all direct reports of i]
    while queue is not empty:
        current = queue.pop()
        count++
        add current's reports to queue
    print count

Why this fails

Imagine the company is a straight line: 1 -> 2 -> 3 -> ... -> 200,000.

To count for Employee 1, we visit 199,999 people.
To count for Employee 2, we visit 199,998 people.
…

This is an Arithmetic Progression. The time complexity is $O(N^2)$. With $N = 200,000$, $N^2 = 40,000,000,000$ operations. This will timeout instantly.

Step 3: The Recursive “Leap of Faith”

We need an $O(N)$ solution. We need to touch every node exactly once.

Notice a pattern?

Employee 2 has 1 subordinate (4).
Employee 1 has Employee 2 on their team.
Therefore, Employee 1 inherits all of Employee 2’s subordinates, plus Employee 2 themselves.

The formula is: $Subordinates(X) = \sum_{child \in Children(X)} (1 + Subordinates(child))$

This is where the Recursive Leap of Faith comes in. When writing the function get_subs(child), we don’t need to know how it calculates the answer. We just assume the contract holds: It will return the correct count.

The Algorithm (DFS Post-Order)

We use a Depth First Search.

Dive to the bottom of the tree (leaf nodes).
Leaf nodes return 0.
Parents sum up the results of their children as the recursion unwinds.

The Solution

Here is the implementation.

import sys

# 1. Essential: Increase recursion depth
# The tree depth can be up to N (200,000), so we set a safe margin.
sys.setrecursionlimit(300000)

def solve():
    # 2. Fast I/O
    # Read all input at once into a list of strings
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    # Use an iterator to consume the input tokens cleanly
    iterator = iter(input_data)
    n = int(next(iterator))
    
    # 3. Build Adjacency List
    # adj[boss] = [list of direct reports]
    # Using size n + 1 for 1-based indexing
    adj = [[] for _ in range(n + 1)]
    
    # The input contains n-1 integers representing bosses for employees 2..n
    for employee in range(2, n + 1):
        boss = int(next(iterator))
        adj[boss].append(employee)
        
    # Array to store the result for each employee
    subordinates = [0] * (n + 1)
    
    # 4. DFS Recursion
    def get_subs(emp):
        count = 0
        for child in adj[emp]:
            # The Logic: My subs = (Child + Child's subs) + Next Child...
            count += 1 + get_subs(child)
        
        subordinates[emp] = count
        return count

    # Start from the General Director (1)
    get_subs(1)
    
    # 5. Print Results (1 to n)
    # The * operator unpacks the list for space-separated printing
    print(*(subordinates[1:]))

if __name__ == '__main__':
    solve()

Alternative Approaches?

Could we do this without recursion?

Iterative DFS: We could simulate the recursion stack manually. This is complex to implement because we need to process the node after visiting children (Post-order), requiring us to manage state carefully.
Topological Sort / Reverse BFS: Since it’s a hierarchy, we could find the “leafs” (nodes with indegree 0 in the reversed graph) and work our way up layer by layer.

However, for Tree problems, simple Recursion is usually the cleanest implementation of the “Divide and Conquer” strategy.

Key Takeaways

Data Structure Choice: An input list of Parent -> Child links is rarely useful. Always convert it to an Adjacency List Parent -> [Children] for traversal.
Pass by Reference: In C++, passing a vector by value copies the whole array. Always use & in recursive functions to avoid TLE.
Trust the Recursion: Don’t try to visualize 200,000 stack frames. Define the base case (leaf), define the recurrence relation, and trust the logic.