bhayanak's blog

help in coloring problem.
By bhayanak, history, 7 years ago, In English

How to solve this simple problem?

You are given a tree of N vertices, and an integer K. How many ways are there to colour the tree with K colours such that no edge is adjacent to vertices of the same colour.

Since the answer may be large, output the answer modulo 1,000,000,007.

Please explain how did u arrive at the result?

  • Vote: I like it
  • +8
  • Vote: I do not like it

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

Answer is

K * (K - 1)(N - 1)

Fix the color of vertex 1 in K ways. For every other vertex, you have K-1 choices.

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

how did you ensure the condition??

no edge is adjacent to vertices of the same colour.

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

    root has k choices.. Then take the nodes at level 1 : they have k-1 choices as it is a tree and there are no cycles Similarly for nodes in level 2 as there can be only one parent, each of them has k-1 choices(excluding the color of its parent node) So root has k choices while the rest of the nodes have k-1 choices and hence you arrive at k*(k-1)^(n-1)

    → Reply