Unirea pentru Performanta XI-XII 2024 | scorpion

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 128MB Input: scorpion.in Output: scorpion.out

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 NN și CC 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 N1N - 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=1C = 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=2C = 2, Ștefan dorește să afle care este scorul maxim pe care l-ar putea avea un arbore construit din NN scânduri, dacă acestea ar fi așezate în mod optim.
Dacă C=3C = 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, NN și CC, reprezentând numărul de scânduri, respectiv numărul cerinței care trebuie rezolvată.
Pe următoarele N1N - 1 linii din fișierul de intrare se găsesc N1N - 1 perechi de numere uiu_i și viv_i, câte o pereche pe câte o linie, cu semnificația că există o muchie între nodurile uiu_i și viv_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=1C = 1, aceasta va conține scorul arborelui inițial.
Dacă C=2C = 2, aceasta va conține scorul maxim al unui arbore cu NN noduri.
Dacă C=3C = 3, aceasta va conține numărul de arbori distinciți cu NN noduri care au scor maxim. Pentru că rezultatul ar putea fi foarte mare se cere afișarea lui modulo 109+710^9+7.

Restricții și precizări

  • 2N300 0002 \leq N \leq 300 \ 000;
  • 1ui,viN1 \leq u_i, v_i \leq N;
  • C=1,2,C = 1, 2, sau 33;
  • Nodul cu numărul 11 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.
# Punctaj Restricții
1 20 C=1C = 1
2 30 C=2C = 2
3 50 C=3C = 3

Exemplul 1

scorpion.in

5 1
1 2
1 3
1 4
1 5

scorpion.out

4

Explicație

Toate cele 44 frunze se află la distanța 11 față de rădăcină. 1+1+1+1=41+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)(1, 2), (2, 3), (3, 4), (3, 5). Frunzele 44 și 55 vor fi la distanța 33 față de rădăcină, rezultând într-un scor de 3+3=63+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.

Log in or sign up to be able to send submissions!