New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Ninja And Cities

Contributed by

Deep Mavani

Hard

0/120

50 mins

50 %

4 upvotes

Problem Statement

Ninja decided to find the distance between the neighbouring cities and then store them for future use. He took data from the map and developed an input format. He is given an integer ‘N’ denoting the number of cities and then he has an array of size ‘N - 1’ that stores a pair of numbers at each index. Let the pair be ‘I1’ and ‘I2’, which will denote a bidirectional edge between the two cities ‘I1’ and ‘I2’.

A subtree is a subset of cities, where each city can be reached from every other city of the subset. The path between each pair passes only though the cities present in the subset. Two subtrees are taken differently if there are one or more cities in one subtree not present in the other.

Now, you need to create an array of ‘N' - 1 elements where the ‘ith’ element is the number of subtrees in which the maximum distance between any two cities is equal to ‘i’.

Note:

1. Note that there exists a unique path between each pair of cites. Also, the final array that you need to create should be 1-indexed, meaning cities with a maximum distance = 1 should be stored on the normal 0th index.

2. Also, note that the distance between two is the number of cities you cross in between.

Example:

Given 'N' = 7, and Array = {[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7]}

So the tree of cities formed in this case would look like:


In the above problem, the subtrees with subsets {[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7]}, have a maximum distance of 1, so put 6 on index 1.

Similarly the subtrees with subsets {[1, 2, 4], [1, 2, 5], [2, 1, 3], [4, 2, 5], [1, 3, 6], [1, 3, 7], [6, 3, 7], [1, 2, 4, 5], [1, 3, 6, 7]} have a maximum distance of 2, so put 9 on index 2.

Now, the subtrees with subsets {[4, 2, 1, 3], [2, 1, 3, 7], [5, 2, 1, 3], [2, 1, 3, 6], [4, 5, 2, 1, 3], [2, 1, 3, 6, 7]} have a maximum distance of 3, so put 6 on index 3.

Now, the subtrees with subsets {[4, 2, 1, 3, 7], [4, 2, 1, 3, 6], [5, 2, 1, 3, 7], [5, 2, 1, 3, 6], [5, 2, 1, 3, 6, 7], [4, 2, 1, 3, 6, 7], [4, 2, 5, 1, 3, 6], [4, 2, 5, 1, 3, 7], [4, 2, 5, 1, 3, 6, 7]} have a maximum distance of 4, so put 12 on index 4.

No subtree has two nodes where the maximum distance between them is 5 and 6 so print 0 on both these indexes.

 Final resultant array = [6, 9, 6, 9, 0, 0]

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases. 

The first line of each test case contains a single integer ‘N’ denoting the number of cities.

The next ‘N - 1’ lines of each test contain an array of ‘N' - 1 pairs where each pair denotes path from ‘I1’ to ‘I2’

Output Format:

For each test case, you need to return ‘N - 1’ space-separated integers where the ‘ith’ element denotes the number of paths in which the maximum distance between the two cities is equal to ‘i’.

Print the output of each test case in a separate line.

Note:

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
2 <= N <= 15
size of array == N - 1
1 <= I1, I2 <= N

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

2 1

Explanation of Sample Output 1:

In test case 1, The tree of cities formed in this case would look like:

In the above problem, the subtrees with subsets {[1, 2], [1, 3]} have a maximum distance of 1, so print 2.

Similarly, the subtrees with subsets {[2, 1, 3]} have a maximum distance of 2, so print 1.

Sample Input 2:

Sample Output 2:

1
3 2 1

Explanation of Sample Output 2:

In test case 1, The tree of cities formed in this case would look like:

In the above problem, the subtrees with subsets {[1, 2]} have a maximum distance of 1, so print 1.

In test case 2, The tree of cities formed in this case would look like:

In the above problem, the subtrees with subsets {[1, 2], [1, 3], [2, 4]} have a maximum distance of 1, so print 3.

Similarly the subtrees with subsets {[1, 2, 4], [2, 1, 3]} have a maximum distance of 2, so print 2.

Now, the subtrees with subsets {[4, 2, 1, 3]} have a maximum distance of 3, so print 1.

Autocomplete

Console