1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Solution
3.1.
C++ implementation
3.1.1.
Input
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

# Stickman Tree

Teesha Goyal
0 upvote

## Introduction

A tree is a data structure in which the elements are stored in hierarchical order. A tree is also defined as a connected acyclic graph or a graph with no cycle. A tree comprises of nodes and edges, where nodes represent the values at that point and edges represent some relation or connection between the nodes.

## Problem Statement

Bob is a little boy who loves to play with graphs. His favourite type of graph is a tree. A tree is a connected graph with no cycle. He has defined a new structure which is called a stickman.

As Bob defined, a stickman is a tree with 7 vertices and 6 edges, in which one vertex must be connected with 4 other vertices and out of these four vertices, one must be connected with two other vertices.

He had a tree of N vertices and counted the number of stickmen in that tree. Two stickmen are distinct if some vertex or some edge is present in exactly one of the two stickmen. The order doesn't matter as long as it fulfils the conditions of the stickman that he defined.

One day a mischievous monkey stole his tree. Now he doesn't remember what his tree looked like. All he remembers is the degree Di of every vertex i of the tree.

Assume that there is a set S of all the random trees with N vertices where the degree of each vertex i is Di. Two trees are distinct if two vertices are connected by an edge in exactly one of the two trees. Now out of all the random trees satisfying the conditions he remembers, help Bob to find the expected number of stickmen in his tree. Find the answer and print it modulo 109 + 7.

Input format

The first line consists of an integer N, the number of vertices in the tree. The following line consists of N integers denoting the degree of each vertex, i.e. D1, D2,..., Dn.

Output format

Print 0 if the expected number of Stickman is 0.

Otherwise, it can be proved that for given constraints, the answer can be uniquely written as a fraction P/Q satisfying conditions:

1) P and Q both are positive integers

2) P and Q are relatively prime (so P/Q is an irreducible fraction)

3) Q is not divisible by 109 +7

Print the value of P * Q-1 modulo 109+7 in a single line.

Constraints

2 <= N <= 105

1 <= Di <= N-1

Note: It is guaranteed that there is at least one tree with the given degrees. So, the described set S isn't empty.

### Example

Input

``````9
4 3 3 1 1 1 1 1 1``````

Output

``428571433``

Explanation

As N=9, there are a total of 9 vertices in the tree. The degree of vertices are given 4,3,3,1,1,1,1,1,1. So there are three groups of trees satisfying the conditions.

1)

This group of trees has Two stickmen, and there can be 90 such trees. Here X represents any node with degree one. So, a total of 180 stickmen from these 90 trees.

2)

For this group, we have 60 different trees, and each tree has one stickman. So, a total of 60 stickmen from these 60 trees.

3)

Similarly, for this group, there are 60 such trees, and each tree has one stickman. So a total of 60 stickmen in 60 trees.

Now, the expected number of stickmen is equal to (180 + 60+ 60)/(90+60+60) = 300/210 = 10/7.

So, P is 10, and Q is 7. We need to print the answer in P * Q-1 modulo 109+7.

Here, 7-1 modulo 109 + 7 = 142857144.

Answer = 10 * 142857144 mod (109+7) = 428571433.

Hence, the output is 428571433.

Also see, Euclid GCD Algorithm

## 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;
}
}
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:

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

Happy Coding!

Live masterclass