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

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.

Poveste şi cerinţă...

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).

h2. Date de intrare

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.

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

h2. Cerinţă

h2. Date de ieşire

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
 
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ă.

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

h2. Restricţii

* $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

* $... ≤ ... ≤ ...$
 
h2. Exemplu

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

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

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

h3. Explicaţie

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") ==