Code : 04

Question 4

You are given a array A of size N. the array is formed using a tree rooted at node 1.

Array generation code:

 Task

Print the number of nodes in the subtree of every node.

Example

Assumptions

·        N = 7

·        A = [1,2,3,4,3,2,1]

Approach

The given array can be formed from a skewed tree, rooted at node 1.

So,

·        The number of nodes in a subtree of 1 = 4.

·        The number of nodes in a subtree of 2 = 3.

·        The number of nodes in a subtree of 3 = 2.

·        The number of nodes in a subtree of 4 = 1.

Function description

Complete the solve function provided in the editor. This function takes the following 2 parameters and returns the array of size N, where the i^th element in the arrayreprensts the number of nodes in subtree of i^th node:

·        N: represents the size of the given array

·        A: represents the given array

 

Input format

 

Note: this is the input format that you must use to provide custom input(available above the Compile and Test button).

·        The first line contains a single integer N

·        The second line contains N integers denoting elements of the array A.

 

Output format

print K space separated integers denoting the number of nodes in the subtree of each node (K is the number of nodes in the tree).

Constraints

1 ≤ A_i,N ≤ 3 x 10⁵

·        It is guaranteed that the tree can be generated using the given input

Code snippets (also called starter code/boiler code)

This question has code snippters for C, CPP, Java and Python.

Explanation

There is an edge between 1 and 2. Thus the subtree count of 1 is 2 while subtree count of 2 is 1.