Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | manuscris.in, manuscris.out | Sursă | Baraj Shumen Seniori ICHB-Vianu - 2022 |
| Autor | Livia Magureanu | Adăugată de |  Comisie Seniori Vianu ICHB •comisie_baraj_shumen_ichb_vianu_seniori |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Manuscris
- Ghoberscris = forma "scrisă" a limbii ghoberiene
- Limba ghoberiană = limba vorbită de ghoberieni
- Ghoberieni = locuitorii tării Ghobera
În această problemă ne interesează în mod special analizarea unor propoziții din limba ghoberiană. Ghoberscrisul este un scris deosebit de impractic, de aceea nici nu a supraviețuit până în zilele noastre.
În primul rând, cuvintele nu sunt reprezentate prin semne grafice, ci prin culori (ghoberienii dispuneau de foarte multe culori).
În al doilea rând, topica propoziției este irelevantă pentru întelesul acesteia. Sensul acesteia este determinat strict de cuvintele care o compun și conexiunile dintre ele.
Din păcate, manuscrisele care s-au păstrat au fost deteriorate de timp și culorile de pe ele au ajuns indescifrabile, însă structura propoziției s-a păstrat.
Dându-se structura unei propoziții (sub formă de arbore) și numărul k de cuvinte / culori distincte din limba ghoberiană, calculați numărul de înțelesuri distincte pe care le putea avea inițial propoziția.
Două înțelesuri se consideră ghober-diferite dacă nu există o reordonare a cuvintelor astfel încât să se obțină doi arbori colorați identic.
Date de intrare
Fişierul de intrare manuscris.in conține pe prima linie două numere, n și k, reprezentând numărul de cuvinte din propoziția dată și respectiv numărul de cuvinte / culori din limba ghoberiană. Pe următoarele n - 1 linii se vor afla câte două numere, a și b cu semnificația că există o conexiune între cuvintele a și b din propoziție.
Date de ieşire
În fişierul de ieşire manuscris.out, pe prima linie, afișați numărul de înțelesuri posibile diferite ale propoziției date.
Restricţii
- 2 ≤ N ≤ 200.000
- 2 ≤ K ≤ 1.000.000
- Pentru teste în valoare de 15 puncte N ≤ 7 și K = 2
- Pentru alte teste în valoare de 5 puncte N = 8 și K = 2
- Pentru alte teste în valoare de 5 puncte N = 9 și K = 2
- Pentru alte teste în valoare de 5 puncte N = 10 și K = 2
Exemplu
| manuscris.in | manuscris.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
