PROBLEM LINKPanel MembersProblem Setter: Sergey Nagin DIFFICULTY: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 EXPLANATIONNumber 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. EXPLANATIONLets 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; for(int i=1; i<adj[u].size(); i++) { if( adj[u][i] != p ) { isleaf = false; dfs(adj[u][i], u); } } 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; for(int i=0; i<adj[u].size(); i++) { if(adj[u][i] != p) { 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. SIMILAR PROBLEMS:Codeforces Testing round 10  D asked 17 Nov '15, 03:08

Que.1 How is O(N M log(M)) supposed to pass ?
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
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)

This is my first experience of writing editorials for Codechef. Please provide your suggestions to make them better. answered 23 Nov '15, 00:16

Kindly check my solution for this. I used the same approach + Fast I/O. Still got TLE. answered 23 Nov '15, 00:31

I used the same approach with simply scanf/printf and it got passed within TL. answered 23 Nov '15, 00:36

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
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

nice editorial, exactly as i thought... but explained in very much detail and lot of mathematical notations.. :p answered 22 Jan '16, 22:08

Can anybody help me with TLE : https://www.codechef.com/viewsolution/10161257 answered 26 May '16, 12:04

Special Thanks for adding similar problem links :D