Unirea pentru Performanta XI-XII 2024 | scorpion

Inspirat de romanul „Cinci săptămâni în balon” al lui Jules Verne, Ștefan decide să pornească el însuși într-o aventură cu balonul cu aer cald deasupra Africii. Din nefericire, acesta este prins într-o furtună de nisip ce duce la prăbușirea lui în marele Deșert Sahara. Până la sosirea ajutoarelor, Ștefan este nevoit să petreacă noaptea singur în deșert. Temându-se de scorpioni, acesta decide să recicleze scândurile rămase de la coșul balonului pentru a-și construi un adăpost.
Ștefan dorește să construiască un adăpost în formă de arbore, care să aibă mult spațiu și să fie departe de sol. Pentru a decide cât de bun este un astfel de adăpost, Ștefan decide să îi aloce un scor egal cu suma distanțelor frunzelor față de rădăcină.

Cerință

Se dau numerele $N$ și $C$ reprezentând numărul de scânduri (noduri) pe care Ștefan le are la dispoziție, respectiv numărul cerinței care trebuie rezolvate, precum și $N - 1$ perechi de numere reprezentând cuiele (muchiile) dintre scândurile (nodurile) arborelui.
Deoarece scândura cu numărul 1 are lățimea cea mai mare, aceasta va fi folosită mereu drept rădăcina arborelui.

Dacă $C = 1$, Ștefan dorește să afle care este scorul actual al arborelui format din scândurile rămase de la coșul balonului.
Scorul se calculează însumând pentru fiecare frunză distanța sa față de rădăcină (nodul cu numărul 1).
Dacă $C = 2$, Ștefan dorește să afle care este scorul maxim pe care l-ar putea avea un arbore construit din $N$ scânduri, dacă acestea ar fi așezate în mod optim.
Dacă $C = 3$, Ștefan se întreabă în câte moduri se poate obține un arbore cu scor maxim. Doi arbori sunt considerați diferiți dacă există cel puțin un nod al cărui tată diferă între cei doi arbori.

Date de intrare

Pe prima linie a fișierului de intrare scorpion.in se găsesc două numere întregi, $N$ și $C$, reprezentând numărul de scânduri, respectiv numărul cerinței care trebuie rezolvată.
Pe următoarele $N - 1$ linii din fișierul de intrare se găsesc $N - 1$ perechi de numere $u_i$ și $v_i$, câte o pereche pe câte o linie, cu semnificația că există o muchie între nodurile $u_i$ și $v_i$.

Date de ieșire

Pe prima linie a fișierului de ieșire scorpion.out se va găsi un singur număr întreg, rezultatul cerinței care trebuie rezolvată.
Dacă $C = 1$, aceasta va conține scorul arborelui inițial.
Dacă $C = 2$, aceasta va conține scorul maxim al unui arbore cu $N$ noduri.
Dacă $C = 3$, aceasta va conține numărul de arbori distinciți cu $N$ noduri care au scor maxim. Pentru că rezultatul ar putea fi foarte mare se cere afișarea lui modulo $10^9+7$.

Restricții și precizări

• $2 \leq N \leq 300 \ 000$;
• $1 \leq u_i, v_i \leq N$;
• $C = 1, 2,$ sau $3$;
• Nodul cu numărul $1$ va fi mereu rădăcina arborelui;
• Se garantează că graful inițial este arbore;
• Doi arbori sunt considerați diferiți dacă părintele al cel puțin unui nod diferă între cei doi arbori.

Exemplul 1

scorpion.in

5 1
1 2
1 3
1 4
1 5

scorpion.out

4

Explicație

Toate cele $4$ frunze se află la distanța $1$ față de rădăcină. $1+1+1+1=4$

Exemplul 2

scorpion.in

5 2
1 2
1 3
1 4
1 5

scorpion.out

6

Explicație

Una dintre cofigurațiile care duce la scorul maxim este cea care are muchiile $(1, 2), (2, 3), (3, 4), (3, 5)$. Frunzele $4$ și $5$ vor fi la distanța $3$ față de rădăcină, rezultând într-un scor de $3+3=6$.

Exemplul 3

scorpion.in

5 3
1 2
1 3
1 4
1 5

scorpion.out

16

Explicație

Una dintre cofigurațiile care duce la scorul maxim este prezentată la exemplul 2.