== include(page="template/taskheader" task_id="muchiipermutate") ==

Poveste şi cerinţă...

Se dă un arbore cu $N$ noduri (numerotate de la $1$ la $N$) şi considerăm muchiile sale numerotate de la $1$ la $N - 1$ (în ordinea în care sunt date în input). Un arbore este un graf neorientat, conex şi aciclic.

h2. Date de intrare

Fie $P$ o permutare a numerelor de la $1$ la $N - 1$. Pentru această permutare $P$ dată, atribuim fiecărei muchii de index $i$ o pondere egală cu $P[i]$. Apoi, considerăm un algoritm în care iniţial nu avem nicio muchie în arbore şi începem să le adăugăm una câte una, în ordinea numerotării lor (practic în ordinea în care sunt date în input, de la $1$ la $N - 1$ - ordinea de adăugare nu depinde de ponderi).

Fişierul de intrare $muchiipermutate.in$ ...

Pentru ca permutarea $P$ să fie considerată validă, la fiecare pas din algoritm se cere ca orice componentă conexă maximală (cu cel puţin $2$ noduri) formată până acum să aibă doar muchii cu ponderi consecutive - aici componentele sunt considerate individual (şi doar cele maximale), deci toate trebuie să respecte condiţia, la orice pas al algoritmului.

h2. Date de ieşire

h2. Cerinţă

În fişierul de ieşire $muchiipermutate.out$ ...

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. Restricţii

h2. Detalii de implementare
 
Concurenţii vor avea de implementat o singură funcţie:
 
== code(cpp) |
std::pair<long long, int> solve(int N, std::vector<int> U, std::vector<int> V);
==
 
care primeşte ca parametri:

* $... ≤ ... ≤ ...$

* $N$, numărul de noduri din arbore;
* Şirurile $U$ şi $V$, unde perechea $U[i], V[i]$ reprezintă capetele muchiei $i + 1$ din arbore (după numerotarea din enunţ), pentru $i$ de la $0$ la $N - 2$.
 
Funcţia $solve$ va fi apelată o singură dată.
 
h2. Restricţii

h2. Exemplu

* $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ă.
 
h2. Punctare
 
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$)
|
| 2
| 4 puncte
| $N ≤ 10$
|
| 3
| 11 puncte
| $N ≤ 500$
|
| 4
| 13 puncte
| $N ≤ 5\ 000$
|
| 5
| 21 puncte
| $N ≤ 200\ 000$ şi arborele este un lanţ (toate nodurile au gradul cel mult $2$)
|
| 6
| 22 puncte
| $N ≤ 200\ 000$
|
| 7
| 27 puncte
| Fără restricţii suplimentare
|
 
h2. Exemple
 
table(example). |_. Fişier de intrare |_. Fişier de ieşire |
| 7
3 7
2 5
2 6
1 3
1 2
2 4
| 2 2
|
| 20
16 17
4 5
8 9
11 12
18 19
1 2
14 15
7 8
19 20
6 7
15 16
3 4
12 13
9 10
2 3
17 18
5 6
10 11
13 14
| 48 8
|
 
h3. Explicaţii

table(example). |_. muchiipermutate.in |_. muchiipermutate.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

Pentru *primul exemplu*, cele două permutări valide optime care respectă constrângerile şi obţin minimul de $2$ inversiuni sunt:

h3. Explicaţie

* $P = (1, 3, 4, 2, 5, 6)$
* $P = (3, 1, 2, 4, 5, 6)$

...

Pentru *al doilea exemplu*, numărul minim de inversiuni al unei permutări valide este $48$ şi există $8$ permutări valide cu acest număr minim de inversiuni.

== include(page="template/taskfooter" task_id="muchiipermutate") ==
 

== include(page="template/taskfooter" task_id="muchiipermutate") ==