×

# Panel Members

Problem Setter: Sergey Nagin
Problem Tester: Istvan Nagy
Editorialist: Sunny Aggarwal
Russian Translator: Sergey Nagin
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

Hard

# PREREQUISITES:

Dynamic Programming, Tree, Memoization, Mathematics.

# PROBLEM:

A tree is an undirected graph on $N$ vertices with $N-1$ edges and no cycles. Let just consider a peculiar way of comparing two trees. To describe it, let's start with the way, we have stored a tree. For every tree $T$, we has a value $V$ — the root of the tree, and for every vertex $i$, we have an ordered list $Q_i$ with $L_i$ elements — $Q_{i, 1}, Q_{i, 2}, ..., Q_{i,L_i}$ which are children of the vertex $i$. We assume that the two trees will be equal if their roots are the same and for every $i$, the ordered list $Q_i$ is the same in both the trees.

Consider the given tree $T_1$ $[V=1, Q_1=[2, 3], Q_2=[], Q_3=[]]$ and $T_2$ given as $[V=1, Q_1=[3, 2], Q_2=[]$$, Q_3=[]], they will be considered different because Q_1 in the first tree is not equal to Q_1 in the second tree. Let us consider that the E_i denotes the number of vertices adjacent to vertex i. Given an array C of N elements, Let f(C) be the number of different trees such that there exists a permutation P_1, P_2, ... , P_N so that E_{P_1} = C_1,$$E_{P_2}= C_2, ... , E_{P_N} = C_N$. We are provided with array $C$ and asked to compute the number $f(C)$ modulo 1000000007 $(10^9+7)$.

# EXPLANATION

It is easy to notice that if $1$ permutation satisfies a configuration of the tree then every possible permutation will satisfy same configuration. So, we will first compute the number of different trees possible for a given permutation say 1, 2, 3, .... N and then will multiply this answer with N!.

Let us consider some notation to understand the solution better. Let us consider a function $F(A)$ denotes the number of different trees possible when there are exactly $A_i$ nodes in each tree with $i$ adjacent nodes. Let us consider another function $G(size, A)$ denotes the number of different tree possible when there are exactly $A_i$ nodes in each tree with $i$ adjacent nodes but each tree root has exactly $size$ number of adjacent nodes.

How to calculate $G(size, A)$ ?

$G(size, A)$ denotes the number of different trees possible (say $T$) when there are exactly $A_i$ nodes in each tree with $i$ adjacent nodes but each tree root ( say $R$) has exactly $size$ number of adjacent nodes. We can compute $G(size, A)$ by choosing a subset of $A$ (say $Z$) and can assign the chosen subset to the first child of root node $R$ and can distribute the remaining set of nodes over the remaining $size-1$ children of root node.

i.e
$$G(size, A) = \sum_{\substack{ Z \subset A }}{F(Z) * G(size-1, A-Z)}$$

How to calculate $F(A)$ ?

$F(A)$ is itself dependent on function. $F(A)$ can be calculated as follows:

i.e
$$F(A) = \sum_{ if (A_i \gt 0) }{G(i, X)}$$

where $X$ = updated $A$ with $X_i = A_i - 1$ as we have selected $1$ node with $i$ adjacent nodes as root.

NOTE: We have received linear time solutions for this problem during the contest. So, Please have a look on them. This is an overview of author's approach. I am still not very much clear with the idea so any suggestions and contributions to this post is welcome.

Exponential Time

# AUTHOR'S AND TESTER'S SOLUTIONS:

The author's solution can be found here.
The tester's solution can be found here.

# SIMILAR PROBLEM

Codechef Problem DEVVOTE

1.7k11730
accept rate: 11%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,212
×711
×139
×107
×95

question asked: 27 Nov '15, 19:02

question was seen: 625 times

last updated: 27 Nov '15, 19:02