CSES 1674 Subordinates - Implementation

Here is the solution:

subtree_size = array of size n

function dfs(node, p):
    subtree_size[node] = 1
    for child in adj[node]:
        if child != p:
            dfs(child, node)
            subtree_size[node] = subtree_size[node] + subtree_size[child]

After running dfs(root, -1), subtree_size[i] holds the size of the subtree rooted at $i$. The number of subordinates is subtree_size[i] - 1.

This runs in $O(n)$ time and uses $O(n)$ space for the subtree size array.