HighC's blog

Doubt #1: Beautiful Tree
By HighC, history, 4 years ago, In English

Hello everyone. I encountered this question in an online test. I could not solve it. Any suggestion for solution will be highly appreciated.

Problem statement

You are given a Tree with n nodes rooted at 1. You are given a value m. You can assign the nodes any value between 1 to m (inclusive). You have to count number of ways to make a Beautiful Tree. A Tree is called a Beautiful Tree, if and only if there exist at-least one root to leaf path, such that GCD of the the values of corresponding nodes in the Path is greater than 1. Since answer can be very large, output answer modulo 10^9 + 7.

Input format:

First line contains two integers n, m. Each of next n-1 lines contains two integers a and b, denoting edge between a and b.

constraints

1 <= n <= 10^5 m < 20

Sample Input:

3 2

1 2

1 3

Sample Output:

3

Explanation:

node 1 (value 2) -> node 2 (value 2) -> node 3 (value 2)

node 1 (value 2) -> node 2 (value 2) -> node 3 (value 1)

node 1 (value 2) -> node 2 (value 1) -> node 3 (value 2)
  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there any constraints provided with the problem?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh yes, My bad. I'll update the post with constraints.

    1 <= n <= (10^5)

    m < 20

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see, I believe a DP solution for this question with $$$O(NM^2)$$$ complexity should exist by calculating the number of trees such that the GCD of all paths from root to leaf is 1.

      → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

My guess is counting the reverse: Trees with all path from root to leaf have gcd 1. Seems like can be done via dp.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks. I guess this is what you are saying right ?

    We have n nodes, m values. Initially we have total (m ^ n) choices. Now we have to subtract GCD 1 cases. which will be

    1. put value 1 at root-1 's value, every root-to-leaf path will have GCD 1. This will count to (m ^ (n-1)).
    2. Put any prime number (p) less than m at root-1's value. discard that prime number. We can put rest m-2 values at n-1 places. This will count to ((m-1) ^ (n-1)).

    So the answer will be (m^n) — (m ^ (n-1)) — p*((m-1) ^ (n-1)). Am i missing something ? But i don't understand why DP .

    Thanks a lot for your suggestion

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      You can put a composite number at root. It just needs to be eventually reduced. E.g. for your sample but m=6, [6,5,5] is also an unbeautiful tree.

      Observation would be that for a subtree, we only care about the gcd from root to the root of subtree. The gcd cannot exceed m, so you can deprive some dp in complexity like n*m^2.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It can be done using dp as mentioned here.

→ Reply