Hello Everyone,
I am trying to solve this problem from Pledge contest going on HackerEarth. I got stucked on this problem http://www.hackerearth.com/tracks/pledge-2015-medium/tree-coloring/ . So, I decided to read the editorial and coded all the thing as mentioned but do not know why i am getting wrong answer. Even my code is exactly similar to the author code . Can anyone help me please.
It has been 4 hours since i am doing this question.. help me ..
Here is my code http://ideone.com/cl9E09
Author solution link : http://ideone.com/eEyDYc
Please copy problem statement here, I don't have access to that page, it's require login.
Its is very simple. Given a rooted tree (root is 1) count the number of its topological ordering .
Nam draws a tree in a paper (Note: tree here is a sinple connected acyclic graph in Graph theory, not tree in reality). The tree consists of N nodes. Nam want to makes his tree more beautiful. Therefore, he decided to coloring all N nodes.
Nam numbering nodes from 1 to N for convinent. He firstly color node 1. Then he will color N — 1 remaining nodes, in any order which satisfied condition: node are chosen to color must be adjacent to one of nodes colored before. Two nodes are consider adjacent if there is a direct edge between them.
Nam wondering, how many ways of coloring the tree he possible make. Two ways are consider different if order of coloring nodes in 2 ways are different, because Nam uses only 1 color.
Input
The first line is T — the number of test cases. Then T test cases follow.
Each test consists of several lines.
The first line is N — the number of nodes in tree. Then the next N — 1 lines, each line contains 2 integer u and v (1 ≤ u, v ≤ N), denoting there is a direct edge between node u and node v. It is guaranteed that these edges form a tree. Output
For each test, print the number of ways coloring the tree in a single line. Since this number can very large, you must print it modulo 109 + 7.
Constraints
1 ≤ T ≤ 10 1 ≤ N ≤ 100000