Stickman Tree

Solution 

Now let's discuss the solution to this problem. We will use a map container from the c++ stl library to solve this problem. We will use Cayley's formula to find the count of distinct trees with the given degrees of each vertex. We will also define two helper functions, power and comb, that will be used a lot. First, we find the number of distinct trees that can be formed with the given degree of vertices then we will find the number of stickmen.

The steps of implementation are:

• Take input of the value of n that is the number of vertices, and then take input the value of Di for each n vertices. Store the value of Di in ctr, a map data structure.
   
• Each for boundary condition, if vertices are less than 7, then print 0.
   
• Initialize variable ans as long long int with value 0.
   
• Implement a For loop over ctr with iterator it1 and implement another inner for loop with iterator it2 while it2 is not equal to the end of ctr and key of it2 is less than or equal to the key of it1.
   
• Call comb function with the arguments - the key of it1-1 and 3, and call again with the key of it2-1 and 2. Find the product of the returned values of a function call and store the modulo of the result with 109 + 7 in stick1.
   
• Exchange the second argument and repeat the previous step and store the result in stick2.
   
• The comb function takes two arguments, n and r. Initialize ans with 1 and run a for loop for i = n-r+1 to n. With Each iteration, update ans first with (ans*i) mod 109 + 7, then ans times (i-(n-r)) raise to the power of 109 + 5 and finally do the modulo of 109 + 7 on ans. Return ans after the for loop ends.
   
• Store the modulo of sum of stick1and stick2 in temp.
   
• If the key of it2 is less than the key of it1, then store the modulo of the product of temp and the value at it1 in c1. And store the modulo of the product of temp and the value at it2 in c2.
   
• Else, again call the comb function with the value of it1 and 2 and store the value in c1. Now find the modulo of the product of c1 and temp and update temp.
   
• Now declare prob as the sum of the keys of it1 and it2 minus 2. Update temp with the modulo of product of temp and prob and update ans and the modulo of sum of ans and temp
   
• Finally, after you come out of the loops. Update ans with the modulo of ans times n-2 raise to the power of 109 + 5 and print ans.

C++ implementation

#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
map <int,int> ctr;

//This function calculates a^b
long long int power(long long int a, long long int b)
{
    if(b == 0)
        return 1;
    if(b == 1)
        return a;
    //by using this we can reduce the complexity to logn
    long long int ans = power(a,b/2);
    ans = (ans*ans)%MOD;
    // if b is odd then we need to multiply it once more
    if(b%2)
        ans = (ans*a)%MOD;
    return ans;
}
long long int comb(int n, int r)
{
    long long int ans = 1;
    for (int i = (n-r)+1; i <= n; ++i)
    {
        ans = (ans*i)%MOD;
        ans = (ans*power(i-(n-r),MOD-2))%MOD;
    }
    return ans;
}
int main()
{
    //Taking input
    int n;
    scanf("%d", &n);
   //Taking the input of the degree of vertices and store it in map ctr
    for (int i = 0; i < n; ++i)
    {
        int x;
        scanf("%d", &x);
        ctr[x]++;
    }
    //check for edge case if number of vertices is less than 7
    if(n < 7)
    {
        printf("0");
        return 0;
    }
    //Initialize ans with 0, this variable is used to store the result
    long long int ans = 0;
    //Loop over the map ctr with iterator it1
    for (map <int,int>::iterator it1 = ctr.begin(); it1 != ctr.end(); ++it1)
//Loop again over the map ctr with iterator it2
    {
        for (map <int,int>::iterator it2 = ctr.begin(); it2 != ctr.end() && it2->first <= it1->first; ++it2)
        {
            long long int stick1 = (comb(it1->first - 1,3)*comb(it2->first - 1,2))%MOD;
            long long int stick2 = (comb(it1->first - 1,2)*comb(it2->first - 1,3))%MOD;
            long long int temp = (stick1 + stick2)%MOD;
            if(it2->first < it1->first)
            {
                long long int c1 = it1->second;
                temp = (temp*c1)%MOD;
                long long int c2 = it2->second;
                temp = (temp*c2)%MOD;
            }
            else
            {
                long long int c1 = it1->second;
                c1 = comb(c1,2);
                temp = (temp*c1)%MOD;
            }
            long long int prob = (it1->first + it2->first - 2);
            temp = (temp*prob)%MOD;
            ans = (ans + temp)%MOD;
        }
    }
//Print the answer 
    ans = (ans*power(n-2,MOD-2))%MOD;
    printf("%lld", ans);
    return 0;
}

Input

9
4 3 3 1 1 1 1 1 1

Output

428571433

Complexities

Time Complexity

O(n^3 *logn), where n is the number of vertices.

Reason:  The complexity of n^2 is because of the two for loops, and then inside the loops, we call the comb function, which we have one for loop, and inside it, the power function is called whose complexity is logn. Therefore the overall complexity is O(n^3logn).

Space Complexity

O(n), where n is the number of vertices.

Reason: To store the degree of vertices, we need a map data structure. Hence the complexity of O(n).

FAQs

1. What is the degree of a node of a tree?

The count of the number of children of a node is defined as the degree of the node. In a binary tree, the maximum degree of a node is 2.
 

2. What is tree data structure?

A tree is a data structure where the elements are not arranged in hierarchical order. It is an acyclic graph with nodes and edges.
 

3. What is a non-linear data structure?

In a Non-linear data structure, the elements are not arranged in a sequential manner. Trees and graphs are examples of non-linear data structures.
 

4. When can we say that the two subtrees are distinct?

Two subtrees are distinct if there are two vertices that are connected by an edge that is present in exactly one of the two trees.
 

5. What is map data structure in C++?

In the C++ Stl library, a map is an associative container where elements are stored in a mapped fashion. Each element of a map has a key and a value. No two values have the same key.

Key Takeaways

In this article, we learned how to solve the problem of "Stickman Tree". We also learned how to use a map from the c++ stl library to solve problems. We used Cayley's formula to find the number of the distinct trees with the desired degree of every vertex. 

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Recommended Problems:

• Graph Valid Tree
• Multiplication Tree
• Largest BST In Binary Tree
• Aggressive Cows
   

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!