×

# 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

medium

# PREREQUISITES:

Dynamic Programming, Number Theory, Trees

# PROBLEM:

Given a rooted tree $T$ consisting of $N$ nodes and an integer $M$. We are asked to calculate the number of ways of putting integers from range $[1, M]$ in each node of the tree $T$ such that for any pair of nodes $\left(A, B\right)$ ( where $A$ is parent of node $B$ ) the number assigned to node $B$ is divisible by the number assigned to node $A$. Since this answer can be very large, Print the answer modulo $10^9 + 7.$

# QUICK EXPLANATION

Number of valid configuration (as mentioned in problem statement) for a tree rooted at a node can be computed from the valid configuration of trees rooted at its children nodes i.e number of ways of assigning a particular number say $K$ to a node say $V$ such that the tree rooted at node $V$ has a valid configuration can be calculated from the number of ways of assigning multiples of number $K$ to the children nodes of $V$ such that trees rooted at children nodes also has a valid configuration.

# EXPLANATION

Lets use some notation to make the explanation more understandable. Let us consider that the function $F_{\left(V, K\right)}$ denotes the number of ways of assigning a number $K$ to the node $V$ such that tree rooted at node $V$ has a valid configuration and the function $D_{\left(V, K\right)}$ denotes the number of ways of assigning any multiple of number $K$ to the node $V$ such that tree rooted at node $V$ has a valid configuration.

Therefore,

$$Required Answer = \bigg(\sum_{\substack{K \in [1, M]}}{F_{\left(1, K\right)}}\bigg) \% 10^9+7$$

How to compute $F_{(V, K)}$ for all $K \in [1, M]$ for any node $V$ ?

As mentioned above, number of ways of assigning a particular number say $K$ to a node say $V$ such that the tree rooted at node $V$ has a valid configuration can be calculated from the number of ways of assigning multiples of number $K$ to the children nodes of $V$ such that trees rooted at children nodes also has a valid configuration.

For any non leaf node $V$,

$$F_{\left(V, K\right)} = \prod_{\substack{U \in children(V)}}{D_{\left(U, K\right)}}$$

otherwise $$F_{\left(V, K\right)} = 1$$

Note that the function $F$ for a node $V$ depends upon the children nodes of $V$.

How to compute $D_{(V, K)}$ for all $K \in [1, M]$ for any node $V$ ?

Let us consider that we have already calculated $F_{(V, K)}$ for all $K \in [1, M]$.

Then, For some $K \in [1, M]$ $$D_{\left(V, K\right)} = \sum_{\substack{Z \in multiple(K)}}{F_{\left(V, Z\right)}}$$

Note that the function $D$ for a node $V$ depends upon the function $F$ for the same node $V$ and can be computed using following simple procedure.

int D[M+1];
int F[M+1];
for(int i=1; i<=M; i++) {
int j = i;
while( j<=M ) {  // iterating over multiples of i
D[i] += F[j];
j += i;
}
}


Look at the following C++ code for the better understanding of above explanation:

int N, M;
int F[N+1][M+1];
int D[N+1][M+1];
void dfs(int u, int p = -1) {
bool isleaf = true;
if( adj[u][i] != p ) {
isleaf = false;
}
}
if( isleaf ) {
// leaf node base case
for(int i=1; i<=m; i++) {
F[u][i] = 1;
}
} else {
// computing function F as per our recurrence
for(int j=1; j<=m; j++) {
int v = 1;
v = 1LL * v * D[adj[u][i]][j];
}
}
F[u][j] = v;
}
}

// computing function D using function F.
for(int i=1; i<=m; i++) {
int j = i;
while( j <= m ) {
D[u][i] += F[u][j];
j += i;
}
}
}


# COMPLEXITY

$O(NM\log(M))$ per test case.

# AUTHOR'S AND TESTER'S SOLUTIONS:

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

# SIMILAR PROBLEMS:

Codeforces Blog Entry

Codeforces round 263 div1 - B

Codeforces Testing round 10 - D

Counting Subgraphs Cook - 63

Counter Strike Contest Codechef

Hackerrank Hack 101

Dynamic Programming on Trees Article

1.7k11630
accept rate: 11%

19.7k350498541

(23 Nov '15, 00:31) 6★

 3 Que.1 How is O(N M log(M)) supposed to pass ? N * M * log(M) = 500 * 20000 * log(20000) = 500 * 20000 * 14 = 14 * 10^7 and there were t = 10 test cases which means total complexity = 10 * 14 * 10^7 = 14 * 10^8 = 14 sec, but time limit was 5 sec. Que.2 Some O(N M log(M)) solutions have had TLE. For example, see my last submission. Was there some trick involved ? link This answer is marked "community wiki". answered 23 Nov '15, 00:11 6★m_17 56●1●6 accept rate: 0% The call to memset() in each test case may be leading to TLE. Also, try to replace modulo with subtractions wherever possible. (23 Nov '15, 00:29) 1 Did everything possible, still TLE. Constraints are too tight. Though I am still wondering if O(N M log(M)) will pass within 5 sec if extreme input is provided. (23 Nov '15, 01:16) m_176★
 0 This is my first experience of writing editorials for Codechef. Please provide your suggestions to make them better. answered 23 Nov '15, 00:16 1.7k●1●16●30 accept rate: 11%
 0 Kindly check my solution for this. I used the same approach + Fast I/O. Still got TLE. answered 23 Nov '15, 00:31 91●1●5 accept rate: 0%
 0 I used the same approach with simply scanf/printf and it got passed within TL. answered 23 Nov '15, 00:36 1.7k●1●16●30 accept rate: 11% nm logm should not. I optimised to make it exactly nm (23 Nov '15, 00:41) kevind1★
 0 My completely recursive code gave TLE then partial recursive and partial iterative gave AC . the constraints should have been less. answered 23 Nov '15, 00:41 1.0k●1●13 accept rate: 4% Please have a look at editorialist solution. It makes use of recursion and still passes all test data in less than 4 sec. (23 Nov '15, 03:17)
 0 My answer during the contest was broadly inline with the editorial. Marked as AC in 4.29 seconds, which was a little lucky. With a few simple optimisation steps Don't calculate remainers %mod unless necessary Remove C++ vector range checking For leaf nodes, optimise the calculation using $F(V,k)=1$, and $D(V,k)=M/k$ When there is just one child node $C$ of a node $V$, then $F(C,k) = D(V,k)$ then run time reduces to 1.19 seconds. However, I'm beginning to believe that each $D(V,k)$ only ever takes about $2\sqrt M$ values as $K$ runs from $1$ to $M$, so the problem can be solved much faster. See ACRush solution in 0.62 seconds. Can anyone provide the explanation? answered 23 Nov '15, 05:42 575●1●7 accept rate: 27%
 0 nice editorial, exactly as i thought... but explained in very much detail and lot of mathematical notations.. :p answered 22 Jan '16, 22:08 100●9 accept rate: 5%
 0 Can anybody help me with TLE : https://www.codechef.com/viewsolution/10161257 answered 26 May '16, 12:04 5★apptica 939●2●10 accept rate: 17%
 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,497
×2,559
×2,093
×1,176
×699
×95
×3

question asked: 17 Nov '15, 03:08

question was seen: 3,673 times

last updated: 26 May '16, 12:04