Number of Ways to Build Empire

Then the King has 3 ways to conquer the world: 0 -> 1 -> 2 -> 3 0 -> 1 -> 3 -> 2 0 -> 2 -> 1 -> 3 All these 3 ways satisfy the constraint that before conquering any kingdom all the kingdoms on the shortest path to the 0th kingdom have been conquered, in other words: before conquering kingdom-3 the King must conquer kingdom-1.

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows: The first line of each test case contains a single integer ‘N’ denoting the number of kingdoms. The next line contains N integers, ‘prevKingdom[i]’ denoting that the ith kingdom can only be reached from the prevKingdom[i]^th kingdom.

For test case 1 : We will return 3, because: ( 0 -> 1 -> 2 -> 3 ) ( 0 -> 1 -> 3 -> 2 ) ( 0 -> 2 -> 1 -> 3 ) are the only possible ways to conquer the world. For test case 2 : We will return 1, because: ( 0 -> 1 -> 2 -> 3 ) is the only possible way to conquer the world.

Depth First Search + Combinatorics

This problem simply wants us to find the number of topological orderings of a directed tree rooted at 0.

Consider a case :

Where we have already precalculated answers for the subtree rooted at nodes 1 and 2.

We have already calculated the ways to order nodes of the subtree rooted at nodes 1 and 2. Nodes numbered as 0 will always be visited before any of the nodes in the subtrees. So the answer of the tree rooted at 0 will be calculated by combining the answer of the subtree rooted at nodes 1 and 2.
Let the ordering of subtree 1 be represented by an array1 of size equal to n1 and ordering of subtree 2 be represented by an array2 of size equal to n2, we can now simply combine array1 and array2 with a constraint that the relative ordering of elements in the original array1 should be not be changed and the same is applied for array 2 also. The number of different orderings we can achieve after combining two fixed arrays will be equal to (n1 + n2)! / ( (n1)! * (n2)! ).
Now let us move a step further, if we know that we can arrange the elements in array1 in p1 ways and we can arrange the elements in array2 in p2 ways, then after combining array1 and array2, then we can say that the number of different ordering is equal to p1 * p2 * ( (n1 + n2)! / ( (n1)! * (n2)! ) ). This happens because after doing step-2, we can just internally permute elements of array1 in p1 ways and elements of array2 in p2 ways.
After understanding the logic of combining two child nodes, we can extend the logic to multiple children: Simply start by taking any two children and combine them, now consider this combined result as a new child and combine all other remaining children with this result one by one.

After understanding this logic the question can simply be tackled by the dfs-algorithm.

Do note that some languages might require you to do inverse modulo calculations. Using Fermat's little theorem we can directly calculate the value of ( (a*b^-1) % p ) as:

( a * ( b ^{(p - 2)} % p ) ) % p )

The steps are as follows :

Precalculate the factorial of all numbers up to ‘N’.
Initialize “adj” to store the tree in form of an adjacency list.
Do depth-first search traversal by making an initial call from the root node. DFS call returns the answer and the number of nodes for the subtree rooted at the current node.
If you reach a leaf node then return {1, 1}.
Initialize “p” and “cnt” to store permutations and the number of nodes for the subtree rooted at the current node. Traverse all the child nodes and use the formula discussed above to calculate “p”. For each traversal update “cnt” so that it finally stores the number of nodes in the subtree.
Finally, return the answer calculated for the root node.

Time Complexity

O( N ), where N denotes the number of kingdoms

We precalculate the factorial and then use depth-first search to visit each kingdom exactly once. Do note that each time we are calculating the inverse modulo expression using binary exponentiation, this involves a complexity of ~log(mod), so the exact time complexity will be O(N*log(1e9)), but ignore the log for a while as mod is explicitly being calculated to fit the answer in integer range.

Hence the time complexity is O( N ).

Space Complexity

O( N ), where N denotes the number of kingdoms

Extra space is required to store the tree in form of an adjacency list.

Hence the space complexity is O( N ).

Number of Ways to Build Empire

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation For Sample Input 1 :

Sample Input 2 :

Sample Output 2 :