# Ninja And Cities

Last Updated: 14 Mar, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### 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]
``````
##### 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
``````

## Approach 1

The simple idea that we use in this approach will be to check all the subsets of cities. For every subset, we will check if it is valid or not. If the subtree is valid, we then find the maximum distance between the two nodes. Now store it according to 1-based indexing.

If for any root, the number of visited nodes equals the number of elements in the subset, it is a valid subtree.

The steps are as follows:

• Create an adjacency matrix let’s say ‘ADJ’ from the given cities or edges.
• Now, calculate the shortest distance from each node to every other node using the Floyd Warshall technique and store it in another 2D array, let’s say ‘DIST’.
• Then generate all the subsets using bit manipulation and for every subset:
• If the size of the subset is greater than one and it is a valid subtree:
• Calculate the maximum distance in that subtree by checking the distance of every node from every other node.
• In order to check if the subtree is valid:
• Create a linear array let’s say ‘VISITED’.
• If the node is not present in the subset:
• ‘VISITED[i]' = 0
• If the node is present in the subset:
• ‘VISITED[i]' = 1
• If the node is visited while doing DFS on the subtree:
• ‘VISITED[i]' = 2
• We start traversing using the DFS approach from any given node in the subset, traversing further to neighbour cities or nodes only if that node is present in the given subset.
• We stop traversing when there are no more options left.
• Using this method, a subset will be valid if all the ‘i’th nodes that initially were ‘VISITED[i]' = 1, are now updated to ‘VISITED[i]' = 2.
• The summation of all the elements in ‘VISITED[]’ will become 2 * size of the given subset.
• If the subtree is valid we return true else false.