muchiipermutate

Muchii Permutate

h2. Cerinţă

Dându-se numărul $N$, reprezentând numărul de noduri din arbore, respectiv cele $N - 1$ muchii ale arborelui (în ordinea din enunţ), să se determine numărul minim de inversiuni dintr-o permutare validă, precum şi numărul de permutări valide care ating acest minim (modulo $10^9 + 7$).

Dându-se numărul $N$, reprezentând numărul de noduri din arbore, respectiv cele $N - 1$ muchii ale arborelui (în ordinea din enunţ), să se determine numărul minim de inversiuni dintr-o permutare validă, precum şi numărul de permutări valide care ating acest minim (modulo $10^9^ + 7$).

h2. Detalii de implementare

h2. Restricţii

* $2 ≤ N ≤ 500\ 000$

* $2 ≤ N ≤ 500 000$

* $1 ≤ U{~i~}, V{~i~} ≤ N$, pentru $0 ≤ i ≤ N - 2$
* *Atenţie*: Doar numărul de permutări valide care au un număr minim de inversiuni se calculează modulo $10^9 + 7$. Pentru numărul minim de inversiuni se calculează valoarea exactă.

table(example). |_. Subtask |_. Punctaj |_. Constrângeri |
| 1
| 2 puncte

| $N ≤ 200\ 000$ şi arborele dat are formă de stea (există un nod de grad $N - 1$)

| $N ≤ 200 000$ şi arborele dat are formă de stea (există un nod de grad $N - 1$)

|
| 2
| 4 puncte

|
| 4
| 13 puncte

| $N ≤ 5\ 000$

| $N ≤ 5 000$

|
| 5
| 21 puncte

| $N ≤ 200\ 000$ şi arborele este un lanţ (toate nodurile au gradul cel mult $2$)

| $N ≤ 200 000$ şi arborele este un lanţ (toate nodurile au gradul cel mult $2$)

|
| 6
| 22 puncte

| $N ≤ 200\ 000$

| $N ≤ 200 000$

|
| 7
| 27 puncte