Tree MEX

All submissions for this problem are available.
Minimum excludant (or MEX for short) of a collection of integers is the smallest nonnegative integer not present in the set. You have a tree $T$ with $n$ vertices. Consider an ordering $P = (v_1, \ldots, v_n)$ of vertices of $T$. We construct a sequence $A(P) = (a_1, \ldots, a_n)$ using the following process:  Set all $a_i = 1$.  Process vertices in order $v_1, \ldots, v_n$. For the current vertex $v_i$ set $a_i = \mathrm{MEX}(a_{u_1}, \ldots, a_{u_k})$, where $u_1, \ldots, u_k$ is the set of neighbours of $v_i$. For instance, let $n = 3$ and $T$ be the tree with edges $(1, 2)$ and $(2, 3)$. Then, for the ordering $P = (1, 2, 3)$ we obtain the sequence $A(P) = (0, 1, 0)$, while for the ordering $P = (2, 3, 1)$ we obtain $A(P) = (1, 0, 1)$. Consider all $n!$ orders $P$. How many different sequences $A(P)$ can we obtain? Print the answer modulo $10^9 + 7$. ###Input: The first line contains an integer $T$, denoting number of test cases. The first line of each test case contains an integer $n$ the number of vertices in the tree ($1 \leq n \leq 10^5$). The following $n  1$ lines describe the tree edges. Each of these lines contains two integers $u_i, v_i$ describing an edge between $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$). ###Output: Print the answer modulo $10^9 + 7$. ###Constraints  $1\le T \le 10$  $1\le n \le 10^5$  $1 \le u_i,v_i \le n$  $u_i \neq v_i$ ###Sample Input: ``` 1 5 1 2 2 3 3 4 4 5 ``` ###Sample Output: `6` ###EXPLANATION: For the sample case, the possible sequences $A(P)$ are $(0, 1, 0, 1, 0)$, $(0, 1, 2, 0, 1)$, $(0, 2, 1, 0, 1)$, $(1, 0, 1, 0, 1)$, $(1, 0, 1, 2, 0)$, $(1, 2, 0, 1, 0$).Author:  vijju123 
Tags  vijju123 
Date Added:  17112018 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 