Subordinates Solution

27 June 2021

Statement

( The original statement can be found here )
Given the structure of a company, your task is to calculate for each employee the number of their subordinates.

Input
The first input line has an integer n: the number of employees. The employees are numbered 1,2,…,n, and employee 1 is the general director of the company. After this, there are n−1 integers: for each employee 2,3,…,n their direct boss in the company.

Output
Print n integers: for each employee 1,2,…,n the number of their subordinates.

Constraints
1 ≤ n ≤ 2⋅10^5
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
5
1 1 2 3

Output :
4 1 1 0 0

Solution

The statement provides a hint when it says that the input is composed of N-1 integers that represent the boss of each employee. This means the company can be represented as a tree with N nodes and N-1 edges.

The problem asks us to calculate the number of subordinates for each employee which can be translated to "compute the size of each node's subtree".
This can be achieved using a recursive algorithm that traverses into the leaf nodes of the tree and sets their subtree size to zero and as the algorithm goes back up the tree it increments the value of the parent's subtree size in such a way that the values build from the bottom level up to the root node like the following animation.

The following expression sums up the process by saying that the subtree size of some node can be calculated by summing all its child's subtree sizes.

#include <bits/stdc++.h>
using namespace std;
#define MAXN 202020

vector<vector<int>> adj(MAXN);
vector<int>subtree_size(MAXN);

int calc (int node) {
   if (adj[node].size() == 0) {
      return 1;
   } else {
       for (int i = 0; i < adj[node].size(); i++) {
          subtree_size[node] += calc(adj[node][i]);
       }
   }
   return subtree_size[node] + 1;
}

int main() {
  int n;
  cin >> n;
  for (int i = 2; i <= n; i++) {
      int boss;
      cin >> boss;
      adj[boss].push_back(i);
  }
  calc(1);
  for (int i = 1; i <= n; i++) {
      cout << subtree_size[i] << " ";
  }
  return 0;
}

Even though this algorithm uses recursion it still runs in time and space complexity of O(N).