PROBLEM LINK:Author: Bipin Baburaj DIFFICULTY:SIMPLE PREREQUISITES:PROBLEM:A rooted tree with N nodes is considered. We need to assign a color from 1 to K to each node of the tree in such a way that every pair of nodes (A,B), where A is the parent of B, has different colors. QUICK EXPLANATION:The answer is $K*(K1)^{N1}$. Note that the actual tree is not given. This is because there is the same answer for every tree with N nodes (and for the given K). EXPLANATION:We can choose any of the K colors for the root of the tree. Then we can choose any color except the root's color for any of the root's children. Then, for every child of a child of the root we can choose any color except that of its parent, and so on. Thus, for each of the other N1 nodes we have K1 choices for its color. The overall answer is $K*(K1)^{N1}$. For subtasks 1 and 2 one can compute the answer in O(N) time. For subtask 3 one needs to compute $(K1)^{N1}$ (modulo $10^9+7$) using fast modular exponentiation, in O(log(N)) time. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 02 Apr '16, 02:48

I have two solutions for the same problem. I applied the exponentiation by squaring method but got a TLE for the use of
My accepted solution uses the answered 11 Apr '16, 18:46
