# Editorial

The structure of the company is a tree. For each vertex $v$ in the tree, determine the number of vertices $sum[v]$ in the subtree where $v$ is the root. The number of subordinates for employee $v$ will be $sum[v]−1$ (since employee $v$ is not his own subordinate).

Initiate a depth-first search starting from vertex $1$, which corresponds to the general director of the company. If $to_{1},to_{2},...,to_{k}$ are the children of vertex $v$, then

If vertex $v$ is a leaf in the tree, set $sum[v]=1$.

Example

Consider the example. Next to each employee (vertex of the graph), the number of their subordinates is indicated.

Algorithm realization

The tree is stored in the adjacency list $g$.

vector<vector<int> > g;

The dfs function performs a depth-first search from vertex $v$ and returns the number of vertices in the subtree rooted at $v$. Vertex $p$ is the parent of $v$ in the depth-first search.

int dfs(int v, int p) {

Initially, the subtree rooted at $v$ contains only the vertex $v$.

sum[v] = 1;

Consider the edge $v→to$. If $to=p$, add to $sum[v]$ the number of vertices in the subtree rooted at $to$.

for (int to : g[v]) if (to != p) sum[v] += dfs(to, v);

Return the number of vertices in the subtree rooted at $v$.

return sum[v]; }

The main part of the program. Read the input data. Construct a tree.

scanf("%d", &n); g.resize(n + 1); for (i = 2; i <= n; i++) { scanf("%d", &x);

For employee $i$, its immediate supervisor in the company is $x$.

g[i].push_back(x); g[x].push_back(i); }

Start the depth-first search from vertex $1$.

sum.resize(n + 1); dfs(1, -1);

Print the answer. The number of subordinates of employee $i$ is equal to $sum[i]–1$.

for (i = 1; i <= n; i++) printf("%d ", sum[i] - 1); printf("\n");

Java realization

import java.util.*; public class Main { static ArrayList<Integer>[] g; static int sum[]; static int n; static int dfs(int v, int p) { sum[v] = 1; for(int to : g[v]) if (to != p) sum[v] += dfs(to,v); return sum[v]; } @SuppressWarnings("unchecked") public static void main(String[] args) { Scanner con = new Scanner(System.in); n = con.nextInt(); g = new ArrayList[n+1]; // unchecked sum = new int[n+1]; for (int i = 0; i <= n; i++) g[i] = new ArrayList<Integer>(); for (int i = 2; i <= n; i++) { int x = con.nextInt(); g[i].add(x); g[x].add(i); } dfs(1,-1); for (int i = 1; i <= n; i++) System.out.print(sum[i] - 1 + " "); System.out.println(); con.close(); } }

Python realization

Increase the stack for recursion.

import sys sys.setrecursionlimit(1000000)

The dfs function performs a depth-first search from vertex $v$ and returns the number of vertices in the subtree rooted at $v$. Vertex $p$ is the parent of $v$ in the depth-first search.

def dfs(v, p):

Initially, the subtree rooted at $v$ contains only the vertex $v$.

sum[v] = 1

Consider the edge $v→to$. If $to=p$, add to $sum[v]$ the number of vertices in the subtree rooted at $to$.

for to in g[v]: if to != p: sum[v] += dfs(to,v)

Return the number of vertices in the subtree rooted at $v$.

return sum[v]

The main part of the program. Read the number of employees.

n = int(input())

Initialize the adjacency list of the graph $g$.

g = [[] for _ in range(n+1)]

Read the input data. Construct a tree.

lst = list(map(int, input().split())) for i in range(2,n+1): a = lst[i-2]

For employee $i(i≥2)$, its immediate supervisor in the company is $a$.

g[a].append(i) g[i].append(a)

Initialize the list $sum$.

sum = [0] * (n + 1)

Start the depth-first search from vertex $1$.

dfs(1,-1)

Print the answer. The number of subordinates of employee $i$ is equal to $sum[i]−1$.

for i in range(1, n+1): print(sum[i] - 1,end=" ")